2017 카카오코드 예선 카카오프렌즈 컬러링북
in Computer Science on Algorithm
문제
class Solution {
static boolean[][] visited;
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,1,-1};
static int row;
static int col;
static int curMax = 1;
public void dfs(int x, int y, int value, int[][] picture){
visited[x][y] = true;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >=0 && ny >=0 && nx<row && ny<col && !visited[nx][ny] && picture[nx][ny] == value){
curMax +=1;
dfs(nx,ny,value,picture);
}
}
}
public int[] solution(int m, int n, int[][] picture) {
int numberOfArea = 0;
int maxSizeOfOneArea = 0;
visited = new boolean[101][101];
row = m;
col = n;
int[] answer = new int[2];
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(picture[i][j] != 0 && !visited[i][j]){
numberOfArea++;
dfs(i,j,picture[i][j],picture);
maxSizeOfOneArea = Math.max(curMax,maxSizeOfOneArea);
curMax = 1;
}
}
}
answer[0] = numberOfArea;
answer[1] = maxSizeOfOneArea;
return answer;
}
}
전형적인 DFS 문제이다.
DFS,BFS 문제는 이미 삼성으로 단련되었기 때문에 비교적 쉽게 풀 수 있었다.
다만 프로그래머스 컴파일러의 한 가지 문제점이 있는데,
전역으로 선언할 때 메모리 할당을 하면 틀렸다고 나오고, 함수 내에서 메모리 할당을 하면 답이 맞게 나오는 아주 황당한 오류가 존재한다.
나도 다 풀고나서 틀렸다고 나오길래 질답게시판을 봤더니 나같은 사람이 꽤 있나보다.
덕분에 도움을 받았다.
(처음에 맞췄을 때 찍어놓을걸)