티스토리 뷰
[Java/Programmers]
Lv.2 카카오프렌즈 컬러링북
(2017 카카오코드 예선)
⬇︎ ⬇︎ ⬇︎ 문 제 링 크 ⬇︎ ⬇︎ ⬇︎
코딩테스트 연습 - 카카오프렌즈 컬러링북
6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5]
programmers.co.kr
입/출력
(입력)
그림의 크기를 나타내는 m 과 n
그림을 나타내는 m × n 크기의 2차원 배열 picture
- 1 <= m, n <= 100
- picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
- picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.
(출력)
원소가 두 개인 정수 배열
answer[0] : 영역의 개수
answer[1] : 가장 큰 영역의 칸의 개수
해결과정
문제는 그래도 빠르게 이해한 것 같은데 어떻게 풀어야 할지 너무 막막해서 풀이 방법에 대해 검색을 했다.
풀이 방법이 딱 정해져있지는 않고 너무 여러가지인데다 이해하기 힘든 부분이 많아 중점적으로 visited(탐색 여부 저장) 배열과 BFS, 재귀로 해결하는 방법이 있다는 세가지 키워드만 얻고 코드를 작성하기 시작했다.
좌표를 저장하는 클래스를 따로 만든 풀이도 있었고, stack과 같은 Collections를 사용해 풀이한 것도 있었는데,
나에겐 너무 어렵게 느껴지고 잘 이해가 안돼 그냥 손으로 그림그려가면서 풀어보려고 했다.
풀이
❌ ver.1 : 테스트 케이스는 돌아가지만 오답인 코드
public static int[] solution(int m, int n, int[][] picture) {
int numberOfArea = 0;
int maxSizeOfOneArea = 0;
// 방문 여부를 저장하는 2차원 배열
boolean[][] visited = new boolean[m][n];
int[] answer = new int[2];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(!visited[i][j] && picture[i][j] != 0) {
numberOfArea++;
int rslt = area(i, j, picture[i][j], visited, picture);
maxSizeOfOneArea = Math.max(maxSizeOfOneArea, rslt);
}
}
}
answer[0] = numberOfArea;
answer[1] = maxSizeOfOneArea;
return answer;
}
public static int area(int m, int n, int color, boolean[][] visited, int[][] picture) {
if (m < 0 || n < 0 || m >= picture.length || n >= picture[1].length) {
return 0;
} else if(visited[m][n]) {
return 0;
} else if(picture[m][n] != color) {
// 여기가 문제!
visited[m][n] = true;
return 0;
} else {
visited[m][n] = true;
return 1 + area(m + 1, n, color, visited, picture)
+ area(m - 1, n, color, visited, picture)
+ area(m, n - 1, color, visited, picture)
+ area(m, n + 1, color, visited, picture);
}
}- area() 함수의 두번째 else if 문에서 color(picture의 원소)값이 다를 경우 visited == true로 하는 부분에서 문제가 있었다.
- 위와 같이 코드를 작성할 경우 다른 영역에 붙어있지만 picture의 원소값이 다른 칸들이 또 다른 영역으로 계산되지 않고 이미 방문이 끝난 것으로 처리돼 영역 개수 계산에서 빠지게 된다. 그러므로 picture의 원소값이 여러개인 일부 테스트 케이스에서 정상적으로 답이 출력되지 않았다.
⭕️ ver.2 : 추가 테스트 케이스를 활용해 고친 정답 코드
public static int[] solution(int m, int n, int[][] picture) {
int numberOfArea = 0;
int maxSizeOfOneArea = 0;
// 방문 여부를 저장하는 2차원 배열
boolean[][] visited = new boolean[m][n];
int[] answer = new int[2];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(!visited[i][j] && picture[i][j] != 0) {
numberOfArea++;
int rslt = area(i, j, picture[i][j], visited, picture);
maxSizeOfOneArea = Math.max(maxSizeOfOneArea, rslt);
}
}
}
answer[0] = numberOfArea;
answer[1] = maxSizeOfOneArea;
return answer;
}
public static int area(int m, int n, int color, boolean[][] visited, int[][] picture) {
if (m < 0 || n < 0 || m >= picture.length || n >= picture[1].length) {
// index가 범위를 벗어난 경우
return 0;
} else if(visited[m][n]) {
// 이미 방문한 경우
return 0;
} else if(picture[m][n] != color) {
// 영역이 붙어 있지만 원소값이 다른 경우
return 0;
} else {
visited[m][n] = true;
return 1 + area(m + 1, n, color, visited, picture) // 아래로 이동
+ area(m - 1, n, color, visited, picture) // 위로 이동
+ area(m, n - 1, color, visited, picture) // 왼쪽으로 이동
+ area(m, n + 1, color, visited, picture); // 오른쪽으로 이동
}
}- 위의 문제가 있었던 visited[m][n] == true; 문장을 제거하고 실행해본 결과 정답을 맞출 수 있었다.
테스트 케이스
public static void main(String[] args) {
int[][] picture = new int[][] {{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}};
int[][] picture1 = new int[][] {{0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}};
int[][] picture2 = new int[][] {{1, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}};
int[][] picture3 = new int[][] {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
int[][] picture4 = new int[][] {{1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 100, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
int[][] picture5 = new int[][] {{1, 1, 1, 0}, {1, 1, 1, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 1}};
int[][] picture6 = new int[][] {{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0}, {0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0}, {0, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 0}, {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0}, {0, 1, 3, 3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 0}, {0, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 0}, {0, 0, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 0}, {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}};
int[] sol = solution(6, 4, picture);
System.out.println(sol[0] + " " + sol[1]);
int[] sol1 = solution(5, 5, picture1);
System.out.println(sol1[0] + " " + sol1[1]);
int[] sol2 = solution(5, 5, picture2);
System.out.println(sol2[0] + " " + sol2[1]);
int[] sol3 = solution(5, 5, picture3);
System.out.println(sol3[0] + " " + sol3[1]);
int[] sol4 = solution(5, 5, picture4);
System.out.println(sol4[0] + " " + sol4[1]);
int[] sol5 = solution(6, 4, picture5);
System.out.println(sol5[0] + " " + sol5[1]);
int[] sol6 = solution(13, 16, picture6);
System.out.println(sol6[0] + " " + sol6[1]);
}- 테스트 케이스 출처는 게시물 맨 밑에 Reference 로 달아놓았다.
테스트 케이스 결과
후기
풀면서 계속 Lv.2가 이렇게 어렵다고? 만 계속 생각했던 것 같다.
다른 분들이 푸신 결과 코드를 보니 내 코드가 나름 짧고 이해하기 쉬운 편인 것 같다. (내가 쓴 코드여서 그런듯)
검색의 도움이 없었다면 나에겐 풀기 힘들었던 난이도라고 생각한다. 더 열심히 코테 연습 해야겠다라는 생각ㅎㅎㅎ....
프로그래머스 내에 테스트 케이스가 하나라 푸는데 더 많은 시간이 소요됐고,
실제로 코테를 볼 때엔 추가적으로 테스트 케이스를 만들어 해결해야 할 것 같다.
✨ Reference ✨
프로그래머스: 카카오 프렌즈 컬러링북
문제https://programmers.co.kr/learn/courses/30/lessons/1829 BFS(너비 우선 탐색) 알고리즘으로 해결 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
jungguji.github.io
'Algorithm' 카테고리의 다른 글
| [Java/Programmers] Lv.1 신규 아이디 추천 (0) | 2021.04.10 |
|---|---|
| [Java/Programmers] Lv.1 두 개 뽑아서 더하기 (0) | 2021.04.09 |
| [Java/Programmers] Lv.1 폰켓몬 (0) | 2021.04.07 |
| [Java/백준(boj)] 2010번. 플러그 (0) | 2021.03.06 |
| [Java/백준(boj)] 1453번. 피시방 알바 (0) | 2021.03.04 |