카카오프렌즈 컬러링북

문제

출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)

그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다.

입력 형식

입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.

1 <= m, n <= 100
picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

출력 형식

리턴 타입은 원소가 두 개인 정수 배열이다. 그림에 몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴한다.

예제 입출력

m	n	picture	answer
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]

예제에 대한 설명

예제로 주어진 그림은 총 4개의 영역으로 구성되어 있으며, 왼쪽 위의 영역과 오른쪽의 영역은 모두 1로 구성되어 있지만 상하좌우로 이어져있지 않으므로 다른 영역이다. 가장 넓은 영역은 왼쪽 위 1이 차지하는 영역으로 총 5칸이다.

문제에 대한 고찰

예시1)
m = 6
n = 4
picture = [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]
answer = [4, 5]

-	`1`	`2`	`3`	`4`
`1`	1	1	1	-
`2`	1	2	2	-
`3`	1	-	-	1
`4`	-	-	-	1
`5`	-	-	-	3
`6`	-	-	-	3

최대크기 1이 5개영역을 차지하고 있기 때문에 5
개수 1/5, 2/2, 1/2, 3/2 즉 4개
답 = [4,5]

예시2)
m = 6
n = 4
picture = [[1, 1, 1, 0], [1, 1, 1, 0], [0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1]]
answer = [2, 6]

-	`1`	`2`	`3`	`4`
`1`	1	1	1	-
`2`	1	1	1	-
`3`	-	-	-	1
`4`	-	-	-	1
`5`	-	-	-	1
`6`	-	-	-	1

최대크기 1이 6개영역을 차지하고 있기 때문에 6
개수 1/6, 1/4 즉2개
답 = [2,6]

문제에 대해 한참을 이해하지 못하고 있다가 그림을 그리면서 고민해보니 생각보다 어렵지 않은 문제였다.
dfs/bfs 우선탐색관련 로직을 기준으로 풀이를 생각해야했다.

1차답안

class Solution {
    static int[] dx = {-1,0,0,1};               // x축이동
    static int[] dy = {0,1,-1,0};               // y축이동
    static boolean[][] check;
    static int cnt;
    
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        check = new boolean[m][n];
        
        for(int i = 0 ; i < m ;i++){
            for (int j = 0 ; j < n ;j++){
                if(picture[i][j] != 0 && !check[i][j]){
                    numberOfArea++;
                    dfs(i,j,picture);
                }
                if(cnt > maxSizeOfOneArea) maxSizeOfOneArea = cnt;
                cnt = 0;
            }           
        }
        
        int[] answer = new int[2];
        
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        
        return answer;
    }
    
     public void dfs(int x, int y, int[][] picture) {
        check[x][y] = true;
        cnt++;
        for(int i = 0; i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= picture.length || ny < 0 || ny >= picture[0].length) continue;

            if(picture[x][y] == picture[nx][ny] && !check[nx][ny]){
                dfs(nx,ny,picture);
            }
        }
    }
}

DFS (깊이우선탐색) vs BFS (너비우선탐색)

그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.
** 여기서 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다.

깊이 우선 탐색 (DFS, Depth-First Search)

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

깊이 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에
해당 분기를 완벽하게 탐색하는 방식을 말합니다.

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가
더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서
그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

너비 우선 탐색 (BFS, Breadth-First Search)

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

너비 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.

깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 비교

BFS	DFS
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

- 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 `DFS`, `BFS` 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다.

- 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 `DFS`를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

- 최단거리 구해야 하는 문제 : 미로 찾기 등 최단거리를 구해야 할 경우, `BFS`가 유리합니다.

- 검색 대상 그래프가 정말 크다면 `DFS`를 고려

- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 `BFS`

JAVA로 구현한 코드

DFS (DFS 알고리즘은 재귀함수를 사용)

함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다.

/* 인접 리스트 이용 */ 
class Graph { 
    private int V; 
    private LinkedList<Integer> adj[]; 
    Graph(int v) { 
        V = v; adj = new LinkedList[v]; // 인접 리스트 초기화 
        for (int i=0; i<v; ++i) 
            adj[i] = new LinkedList(); 
    } 
    
    void addEdge(int v, int w) { 
        adj[v].add(w); 
    } 
    /* DFS */ 
    void DFS(int v) { 
        boolean visited[] = new boolean[V]; 
        // v를 시작 노드로 DFSUtil 재귀 호출 
        DFSUtil(v, visited); 
    } 

    /* DFS에 의해 사용되는 함수 */ 
    void DFSUtil(int v, boolean visited[]) { 
        // 현재 노드를 방문한 것으로 표시하고 값을 출력 
        visited[v] = true; 
        System.out.print(v + " "); 
        // 방문한 노드와 인접한 모든 노드를 가져온다. 
        Iterator<Integer> it = adj[v].listIterator(); 
        while (it.hasNext()) { 
            int n = it.next(); 
            // 방문하지 않은 노드면 해당 노드를 시작 노드로 다시 DFSUtil 호출 
            if (!visited[n]) 
                DFSUtil(n, visited); 
        } 
    } 
}

BFS (BFS 알고리즘은 큐(Queue)를 사용)

class Graph { 
    private int V; 
    private LinkedList<Integer> adj[];
    Graph(int v) { 
        V = v; 
        adj = new LinkedList[v]; 
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList(); 
    } 
    
    void addEdge(int v, int w) { 
        adj[v].add(w); 
    } 
    
    /* BFS */ 
    
    void BFS(int s) { 
        boolean visited[] = new boolean[V]; 
        //방문여부 확인용 변수 
        LinkedList<Integer> queue = new LinkedList<Integer>(); 
        //연결리스트 생성 
        visited[s] = true; 
        queue.add(s); 
        while (queue.size() != 0) { 
            // 방문한 노드를 큐에서 추출(dequeue)하고 값을 출력 
            s = queue.poll(); 
            System.out.print(s + " "); 
            // 방문한 노드와 인접한 모든 노드를 가져온다. 
            Iterator<Integer> i = adj[s].listIterator(); 
            while (i.hasNext()) { 
                int n = i.next(); 
                // 방문하지 않은 노드면 방문한 것으로 표시하고 큐에 삽입(enqueue) 
                if (!visited[n]) { 
                    visited[n] = true; 
                    queue.add(n); 
                }
            }
        } 
    } 
}

참고 URL