[ Baekjoon - 10/01 ] - 16724번: 피리 부는 사나이

• 문제 링크 : https://www.acmicpc.net/problem/16724

16724번: 피리 부는 사나이

 

• 소요 시간 : 3시간 (Union-Find 문제가 오랜만이라 구현에 시간을 많이 쏟았다..ㅜ 어려워어려워)

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 256MB
   • 문제
     • 지도의 행(1≤N≤1,000), 지도의 열(1≤M≤1,000)
     • 영과일(?) 회원들이 지도의 각 방향에 따라 이동할때 모두가 SAFE ZONE에 들어갈 수 있게하는 SAFE ZOON의 최소 개수를 구하는 문제
   • 이해
     • 글로만 읽었을때는 이해가 쉽사리 되진 않았던 문제인것같다. 어디에서 출발한다는 말도 없고 방향만 주어져있어서 문제를 여러번 읽고 입출력예제를 그려보며 이해하려고 했다. 
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 입력 예제가 영어라서 보기 어려워 이를 방향으로 나타내보았고, 연결이 가능한 방향을 길게 이어보았다.
     그랬을때, 이어지지않는 독립적인 사이클이 3개가 나왔고 이를 연결하기위해서는 2개의 SAFE ZOON이 있으면 되니, 사이클에서 1을 빼면 답이 구해질것이라 추측할 수 있었다.
3. 문제를 어떻게 해결할 것인가

   • 

   • 1st 접근 - DFS )
     • 사이클도 결국은 구획을 나누는 것이기 때문에 BFS로 가능하다고 생각했다. 같은 루프라면 같은 숫자를 넣어 구분하도록 하면 영역(사이클) 구분은 가능해 보였다.
     • 하지만 사실상 방문이 가능한 곳(BFS에서는 방문 할 곳을 저장하므로)은 방향에 따라 갈수있는 한곳 뿐이므로 BFS보단 DFS가 적합하다고 생각했다. 반복문 돌리면서 방문하지 않은곳이면 dfs를 가면 되니까.
     • DFS로 해결가능하다고 생각했지만, 사실상 완탐이므로 좀더 효율적인 방법이 없는지 생각했다.
       <후에 위 문제를 DFS로도 도전해보려 한다>
   • 2st 접근 - Union-FInd )
     • 완탐이 아닌 다른 방법을 생각해도 딱히 떠오르지 않아서 알고리즘 분류를 참고했는데, 집합이라는 단어가 보였다.
     • 집합, 같은 사이클이면 같은 집합, 합집합,루트... 생각하다가 Union-FInd 연산이 생각났고 이를 이용하면 좀더 효율적인 구현이 가능할것이라 생각했다!
     • 위 문제는 2차원 배열로 주어져서 조금 까다롭지만 좌표당 하나의 객체라 생각하면 이해는 쉬웠다. (코드 구현은 어려웠지만..)
     • 위 그림의 Union-Find의 1번은 각 배열을 본인을 가르키도록(본인만 있는 트리에선 본인이 루트) 초기화한 상태를 그림으로 그려보았다.
       [코드로는, N*M개의 1차원배열(u)에 각 인덱스(i)와 본인(u[i])이 같게 넣어주는 작업이다.] - 2차원도 가능
     • 2번에서는 (0,0)기준으로 보았을때 밑으로 움직일 수 있으므로(갈수있음) (1,0)인 노드와 같은 사이클이다.
       하지만 아직 (0,0)의 루트는 자기자신이고, (1,0)의 루트도 자기자신이므로 합집합 연산을 해주어 같은 사이클이 되도록 연결해주어야한다. 
       [코드로는, (1,0)의 루트(u[j])에 (0,0)의 루트(u[i])를 대입하는 과정이다.]
     • 계속 같은 방식으로 map을 전부 방문할 때까지 반복해주면 된다.
4. 위 계획을 검증
   • 같은 사이클인 노드를 합하여 하나의 집합으로 저장하면, 결국 집합의 개수가 사이클의 개수가 되므로, 성립한다.
5. 계획 수행 (실제코드 작성) 
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main{
            static int N,M;
            static char[][] map;
            static int[] u;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
        
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st = new StringTokenizer(br.readLine());
                N = Integer.parseInt(st.nextToken());
                M = Integer.parseInt(st.nextToken());
        
                map = new char[N][M];
                u = new int[N*M];
                for (int i = 0; i < N*M; i++) {
                    u[i] = i;
                }
                for (int i = 0; i < N; i++) {
                    map[i] = br.readLine().toCharArray();
                }
        
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++) {
                        int curIdx = i*M+j;
                        int nextIdx = findIdx(i,j);
                        if(findRoot(curIdx) != findRoot(nextIdx)){
                            union(curIdx, nextIdx);
                        }
                    }
                }
                HashSet<Integer> set = new HashSet<>();
                for (int i = 0; i < u.length; i++) {
                    set.add(findRoot(i));
                }
                System.out.println(set.size());
            }
        
            private static int findIdx(int i, int j) {
                if(map[i][j] =='U'){
                    i--;
                }else if(map[i][j] =='D'){
                    i++;
                }else if(map[i][j] =='L'){
                    j--;
                }else if(map[i][j] =='R'){
                    j++;
                }
                return i*M+j;
            }
        
            private static void union(int curNode, int nextNode) {
                int cur = findRoot(curNode);
                int next = findRoot(nextNode);
                if(curNode>nextNode){
                    u[cur] = next;
                }else{
                    u[next] = cur;
                }
            }
        
            private static int findRoot(int idx) {
                if(u[idx] == idx)
                    return idx;
                else
                    return u[idx] = findRoot(u[idx]);
            }
        }

      • 보통 집합은 1차원으로만 접근했었는데 위 문제는 2차원배열이므로, 1차원으로 바꿔 생각한다고 시간도 많이 잡아먹었다. 하지만 투자한 시간만큼 간결하고 가독성 좋은 코드는 나오지 않아서 다시 자바로 풀어보고 이를 파이썬으로도 풀어볼 예정이다.

 

 

• 결과