카카오 프렌즈 컬러링북
- https://programmers.co.kr/learn/courses/30/lessons/1829
본 게시글은 본 저작자의 저작권 보호를 위해 동일 유형의 가상의 문제를 만들어 풀이합니다. bfs라는 알고리즘 자체에 대한 저작권은 일반적으로 인정되지 않으며 않으며 문제에 표현된 생각이나 감정은 모두 제가 생각한 새로운 것으로 새로운 저작물로 취급됩니다.
따라서 가상 문제의 저작권은 블로그 운영자가 가지며 모든 권한을 가집니다.
동일 유형 유사 문제. 해양 탐험가의 산호초 모자이크
해양 탐험가인 마린은 카일에게 산호초 모자이크 책에 들어갈 디자인을 그려달라고 부탁하여 여러 장의 디자인을 받았다. 모자이크의 색은 숫자로 표현된다. 여러 장의 디자인을 복잡성 순으로 모자이크 책에 넣고 싶었던 마린은 구역이 많으면 색칠하기가 번거로워 어려워진다는 사실을 발견하고 디자인의 복잡성을 구역의 수로 정의하였다.
구역은 상하좌우로 연결된 같은 패턴의 공간을 의미한다.
디자인에 몇 개의 구역이 있는지와 가장 큰 구역의 크기는 얼마인지 계산하는 프로그램을 작성해보자.
1
2
3
4
5
6
7
8
9
+-+-+-+-+
|1|2|2|3|
+-+-+-+-+
|1|1|3|6|
+-+-+-+-+
|4|5|5|6|
+-+-+-+-+
|4|4|6|6|
+-+-+-+-+
위의 디자인은 총 6개 구역으로 이루어져 있으며, 가장 큰 구역은 6으로 크기는 4이다.
입력 형식
입력은 디자인의 크기를 나타내는 m과 n, 그리고 디자인을 나타내는 m × n 크기의 2차원 배열 pattern으로 주어진다. 제한조건은 아래와 같다.
1 <= m, n <= 50
pattern의 원소는 0 이상 100 이하의 임의의 값이다.
pattern의 원소 중 값이 0인 경우는 색칠하지 않는 구역을 뜻한다.
출력 형식
출력 타입은 원소가 두 개인 정수 배열이다. 디자인에 몇 개의 구역이 있는지와 가장 큰 구역은 몇 칸으로 이루어져 있는지를 출력한다.
유사 유형 문제 풀이
pattern[rol][col]==-1이 아닌 지점을 기준으로 같은 값의 영역을 계속 -1로 만들면서 탐색하는 bfs 알고리즘을 사용했다.
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
import java.util.*;
class Solution {
static Queue<int[]> queue;
public int[] solution(int m, int n, int[][] pattern) {
int numberOfArea = 0;
int maxSizeOfOneArea = 0;
int[][] cpic = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cpic[i][j] = pattern[i][j];
}
}
queue = new LinkedList<>();
int temp = 0;
for(int i =0, j=0; i<m; i++){
for(j=0; j<n; j++){
temp = bfs(i,j,m,n, cpic);
if(temp > 0) {
numberOfArea++;
maxSizeOfOneArea = Math.max(temp, maxSizeOfOneArea);
}
}
}
int[] answer = new int[2];
answer[0] = numberOfArea;
answer[1] = maxSizeOfOneArea;
return answer;
}
// pattern[rol][col]==-1이 아닌 지점을 기준으로 같은 값의 영역을 계속 -1로 만들면서 탐색하는 bfs
private int bfs(int row, int col, int m, int n, int[][] pattern){
if(pattern[row][col] == 0)
return 0;
int thisColor = pattern[row][col];
queue.offer(new int[]{row,col});
pattern[row][col] = 0;
int sum = 0;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while(!queue.isEmpty()){
int[] pos = queue.poll();
int trow = pos[0], tcol = pos[1];
sum++;
for(int d=0; d<4; d++){
int nr = trow + dr[d];
int nc = tcol + dc[d];
if(nr == -1 || nr == m || nc == -1 || nc == n || pattern[nr][nc] == 0 || pattern[nr][nc] != thisColor)
continue;
queue.offer(new int[]{nr,nc});
pattern[nr][nc] = 0;
}
}
return sum;
}
}