[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인것만 다시 밟지 않으면된다.
코드
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;
}
}