PGMS_가장 큰 삼각형 덩어리 (Java)
[level 4] 가장 큰 삼각형 덩어리 - 389629
성능 요약
메모리: 121 MB, 시간: 89.95 ms
구분
코딩테스트 연습 > 2025 프로그래머스 코드챌린지 본선
채점결과
정확성: 100.0
합계: 100.0 / 100.0
제출 일자
2025년 03월 07일 20:11:02
문제 설명
N행 M열의 2차원 격자 grid가 주어집니다. 격자의 각 칸은 한 변의 길이가 √2인 정사각형이며, 각 칸 안에는 대각선이 하나 그어져 있습니다. 이 대각선은 / 방향(1) 또는 \ 방향(-1) 중 하나입니다.
각 정사각형 칸은 대각선에 의해 동일한 크기의 직각삼각형 두 개로 나뉘며, 당신은 각 칸에서 두 삼각형 중 정확히 하나만 색칠할 수 있습니다. 색칠된 삼각형들은 한 '변'을 공유해야 서로 연결되며, 이렇게 연결된 삼각형들의 집합을 하나의 삼각형 덩어리라고 합니다.
당신의 목표는 격자 전체를 적절히 색칠하여, 연결된 하나의 삼각형 덩어리 중 가능한 가장 큰 덩어리의 넓이를 구하는 것입니다. 각 삼각형의 넓이는 칸을 이루는 정사각형의 면적(2)의 절반인 1입니다. 따라서 덩어리에 포함된 삼각형의 개수가 곧 그 덩어리의 넓이가 됩니다.
격자의 상태를 나타내는 2차원 정수 배열 grid가 매개변수로 주어집니다. 이 격자를 적절히 색칠했을 때, 만들 수 있는 삼각형 덩어리들 중에서 가장 넓이가 큰 덩어리의 넓이를 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤
grid의 세로 길이 =N≤ 200,000 - 1 ≤
grid의 가로 길이 =M≤ 200,000 - 1 ≤
N×M≤ 200,000 grid[i][j]는 -1, 1 중 하나의 값을 가집니다.grid[i][j]가 -1이면 \ 방향을 나타내며, 1이면 / 방향을 나타냅니다.
테스트 케이스 구성 안내
아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.
| 그룹 | 총점 | 추가 제한 사항 |
|---|---|---|
| #1 | 50% | N × M ≤ 20 |
| #2 | 50% | 추가 제한 사항 없음 |
입출력 예
| grid | result |
|---|---|
| [[-1, -1, -1], [1, 1, -1], [1, 1, 1]] | 5 |
| [[1, -1, 1], [-1, 1, -1]] | 4 |
| [[1]] | 1 |
입출력 예 설명
입출력 예 #1
격자의 상태는 아래 그림과 같습니다.
각 칸에서 한 개의 삼각형을 적절히 색칠했을 때, '하나로 연결된 삼각형 덩어리' 중 넓이가 가장 큰 경우는 아래 그림에서 색칠된 부분과 같습니다. 이 경우 덩어리의 넓이는 5이므로, 5를 return 해야 합니다.
입출력 예 #2
격자의 상태는 아래 그림과 같습니다.
각 칸에서 한 개의 삼각형을 적절히 색칠했을 때, '하나로 연결된 삼각형 덩어리' 중 넓이가 가장 큰 경우는 아래 그림에서 색칠된 부분과 같습니다. 이 경우 덩어리의 넓이는 4이므로, 4를 return 해야 합니다.
입출력 예 #3
최대 1개의 삼각형을 색칠할 수 있습니다. 삼각형 하나의 넓이인 1을 return 합니다.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
문제 풀이
대각선에 상태가 1과 -1이 있고, 각 칸마다 2개의 삼각형으로 나뉜다. 이때 대각선 1에 의해 나뉜 삼각형을 왼쪽부터 1과 2, 대각선 -1에 의해 나뉜 삼각형을 왼쪽부터 -1, -2로 설정했다. 이후 각 삼각형마다 어떤 방향으로 갈 수 있는지 살펴보면
- 부분삼각형 1 : 왼쪽, 위
- 부분삼각형 2 : 오른쪽, 아래
- 부분삼각형 -1 : 왼쪽, 아래
- 부분삼각형 -2 : 오른쪽, 위
1과 2를 보고 각 격자에 어떤 대각선이 있는지도 알 수 있으며 각 삼각형을 만난 순간 어떤 방향으로 진행해야하는지도 알 수 있다. 이렇게 다음 진행해야할 방향을 nextDir로 만든 뒤 사용했다.
그리고 한 격자에서 한개의 삼각형만 사용할 수 있으므로 2차원 visited로 격자 방문처리도 해주었고, 이전에 방문했더라도 bfs돌면서 다시 방문할 순 있기 때문에 그 bfs메서드 도는 순간에만 일회용으로 방문처리를 해주어야했다. 처음에는 HashSet에서 매번 생성해 visited를 해주었는데 오버헤드가 커 3개의 테스트케이스에서 시간초과가 발생했다. 이를 bfs마다 id를 부여해 int[][] visited로 처리해줬다. bfsId 가 k일때 k인것만 다시 밟지 않으면된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
import java.util.*;
class Solution {
static int N, M, max=Integer.MIN_VALUE, bfsCnt=1;
static int[] dr = {0, -1, 0, 1}, dc = {-1, 0, 1, 0}; // 좌 상 우 하
static int[][][] board;
static int[][] visited;
static int[][] nextDirs;
public int solution(int[][] grid) {
int res = 0;
N = grid.length;
M = grid[0].length;
board = new int[N][M][2];
visited = new int[N][M];
nextDirs = new int[2][3]; // [r, c, nextState]
// 각 칸마다 2개의 삼각형이 존재
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
// "/" 모양 : 1
if(grid[i][j] == 1){
board[i][j][0] = 1;
board[i][j][1] = 2;
}
// "\"모양 : -1
else{
board[i][j][0] = -1;
board[i][j][1] = -2;
}
}
}
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
for(int k=0; k<2; k++){
if(visited[i][j] == 0){
// System.out.println("시작점 : " + i + " , " + j + " , " + "방향 : " + k);
int cnt = bfs(i, j, k, grid, bfsCnt++);
if(cnt > max) max = cnt;
}
}
}
}
return max;
}
// bfs 메서드
private static int bfs(int r, int c, int pos, int[][] grid, int bfsId){
int cnt = 1;
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] {r, c, pos});
visited[r][c] = bfsId;
while(!queue.isEmpty()){
int[] curr = queue.poll();
int currState = board[curr[0]][curr[1]][curr[2]];
int idx = getNext(curr[0], curr[1], currState, grid);
for(int i=0; i<idx; i++){
int nextR = nextDirs[i][0];
int nextC = nextDirs[i][1];
int nextState = nextDirs[i][2]; // -2, -1, 1, 2
int nextP = (int) Math.abs(nextState) %2 == 1 ? 0 : 1; // 0 or 1
if(!isValid(nextR, nextC)) continue;
if(visited[nextR][nextC] == bfsId) continue;
visited[nextR][nextC] = bfsId;
queue.offer(new int[] {nextR, nextC, nextP});
cnt++;
}
}
// System.out.println("cnt : " + cnt);
return cnt;
}
private static int getNext(int r, int c, int state, int[][] grid){
int dirCnt = 0;
// 4가지 종류의 삼각형에 대해 다음 방향을 결정
if(state == 1){ // 좌, 상
int nextR = r + dr[0];
int nextC = c + dc[0];
if(isValid(nextR, nextC)){
nextDirs[dirCnt][0] = nextR;
nextDirs[dirCnt][1] = nextC;
int nextState = grid[nextR][nextC]==1 ? 2 : -2;
nextDirs[dirCnt][2] = nextState;
dirCnt++;
}
nextR = r + dr[1];
nextC = c + dc[1];
if(isValid(nextR, nextC)){
nextDirs[dirCnt][0] = nextR;
nextDirs[dirCnt][1] = nextC;
int nextState = grid[nextR][nextC]==1 ? 2 : -1;
nextDirs[dirCnt][2] = nextState;
dirCnt++;
}
}
else if(state == 2){ // 우, 하
int nextR = r + dr[2];
int nextC = c + dc[2];
if(isValid(nextR, nextC)){
nextDirs[dirCnt][0] = nextR;
nextDirs[dirCnt][1] = nextC;
int nextState = grid[nextR][nextC]==1 ? 1 : -1;
nextDirs[dirCnt][2] = nextState;
dirCnt++;
}
nextR = r + dr[3];
nextC = c + dc[3];
if(isValid(nextR, nextC)){
nextDirs[dirCnt][0] = nextR;
nextDirs[dirCnt][1] = nextC;
int nextState = grid[nextR][nextC]==1 ? 1 : -2;
nextDirs[dirCnt][2] = nextState;
dirCnt++;
}
}
else if(state == -1){ // 좌, 하
int nextR = r + dr[0];
int nextC = c + dc[0];
if(isValid(nextR, nextC)){
nextDirs[dirCnt][0] = nextR;
nextDirs[dirCnt][1] = nextC;
int nextState = grid[nextR][nextC]==-1 ? -2 : 2;
nextDirs[dirCnt][2] = nextState;
dirCnt++;
}
nextR = r + dr[3];
nextC = c + dc[3];
if(isValid(nextR, nextC)){
nextDirs[dirCnt][0] = nextR;
nextDirs[dirCnt][1] = nextC;
int nextState = grid[nextR][nextC]==-1 ? -2 : 1;
nextDirs[dirCnt][2] = nextState;
dirCnt++;
}
}
else{ // -2, 상, 우
int nextR = r + dr[1];
int nextC = c + dc[1];
if(isValid(nextR, nextC)){
nextDirs[dirCnt][0] = nextR;
nextDirs[dirCnt][1] = nextC;
int nextState = grid[nextR][nextC]==-1 ? -1 : 2;
nextDirs[dirCnt][2] = nextState;
dirCnt++;
}
nextR = r + dr[2];
nextC = c + dc[2];
if(isValid(nextR, nextC)){
nextDirs[dirCnt][0] = nextR;
nextDirs[dirCnt][1] = nextC;
int nextState = grid[nextR][nextC]==-1 ? -1 : 1;
nextDirs[dirCnt][2] = nextState;
dirCnt++;
}
}
return dirCnt;
}
private static boolean isValid(int r, int c){
return r >= 0 && r < N && c >= 0 && c < M;
}
}