백준 15559 (내 선물을 받아줘) - java

https://www.acmicpc.net/problem/15559

15559번: 내 선물을 받아줘

 

문제

욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다.

구사과가 있는 곳은 N×M 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (i, j)로 나타낼 수 있으며, (i, j)는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸을 의미한다.

지도의 각 칸에는 N, W, E, S 중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한다. 구사과의 위치가 (i, j)인 경우에 N이 쓰여져 있는 칸에 서 있었다면, (i-1, j)로, S의 경우에는 (i+1, j)로, W의 경우에는 (i, j-1), E의 경우에는 (i, j+1)로 순간이동한다. 구사과는 지치지 않기 때문에, 계속해서 이동한다.

욱제는 구사과의 위치를 모르기 때문에, 구사과가 이동을 시작하는 위치와 관계없이 선물을 주는 방법을 알아내려고 한다. 최소 몇 개의 칸 위에 선물을 놓으면, 구사과가 항상 선물을 가져가는지 구하는 프로그램을 작성하시오. 선물이 놓여진 칸에 구사과가 이동하면, 구사과는 항상 선물을 가져간다.

 

유형 : 그래프 탐색 + 분리 집합

 

접근 방식

• 우선 위 격자를 이동하는 와중에 격자를 벋어나는 경우는 없다. (문제에 나와있음)
• 문제를 틀리는 가장 큰 이유는 그래프의 탐색 횟수 가 정답일거라는 생각에서 비롯된다.
  • 위 문제에서 중요한 점은 선물을 놓을 경우 항상 가져가는 위치이기 때문에 겹치는 경로가 발생하게 된다.

(1,1) -> (1,2) -> (1,3)
           ^
(2,1) -> (2,2)

 

위와 같은 경우에 그래프의 탐색 횟수는 2번이다. 하지만 정답은 1이다. (1,2)나 (1,3)에 선물을 놓으면 어느 위치에서 출발해도 사과를 가져갈 수있다. 

즉 겹치는 경우도 생각해줘야 한다.

 

방법 : Union - Find

• 각 그래프 탐색에 번호를 부여하고 만약 이전에 탐색한 지점을 찾은 경우 부모로 지정하여 결과적으로 횟수를 줄이는 것이다.
• 사실 DFS를 사용하면 이런 작업은 필요없다..... 하지만 나는 이 문제를 BFS를 활용하여 해결하였기 때문에 이렇게 설명하겠다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int[][] board;

    static int[][] v;

    static int[] dx = {-1,1,0,0}; // N S W E
    static int[] dy = {0,0,-1,1};

    static HashMap<Integer,Integer> root = new HashMap<>();

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board= new int[n+1][m+1];
        v = new int[n+1][m+1];

        for(int i=1;i<=n;i++){
            String line = bf.readLine();

            for(int j=1;j<=m;j++){
                char cur = line.charAt(j-1);

                if(cur == 'N'){
                    board[i][j] = 0;
                }else if(cur == 'S'){
                    board[i][j] = 1;
                }else if(cur == 'W'){
                    board[i][j] = 2;
                }else{
                    board[i][j] = 3;
                }
            }
        }

        int num = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(v[i][j] ==  0){
                    root.put(num,num); // 방문하지 않은 곳을 탐색시 회차의 root 초기화
                    bfs(i,j,num); // 탐색
                    num +=1; // 다음 회차의 번호 증가
                }
            }
        }

        HashSet<Integer> set = new HashSet<>();

        for(int i=1;i<num;i++){
            set.add(root.get(i)); // 중복 제거
        }
        System.out.println(set.size());


        bf.close();
    }

    static void bfs(int i,int j,int num){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(i,j));
        v[i][j] = num;

        while(!q.isEmpty()){
            Node cur = q.poll();

            int nx = cur.x + dx[board[cur.x][cur.y]];
            int ny = cur.y + dy[board[cur.x][cur.y]];

            if(v[nx][ny] == 0){
                v[nx][ny] = num;
                q.add(new Node(nx,ny));
            }else{
                union(num,v[nx][ny]); // 이전에 탐색한 곳이라면 Union - Find
                break;
            }
        }
    }

    static int find(int x){
        if(x == root.get(x))
            return root.get(x);

        // return root[x] = find(root[x]);
        root.put(x,find(root.get(x)));

        return root.get(x);
    }

    static void union(int x,int y){
        x = root.get(x);
        y = root.get(y);

        if(x < y){
            root.put(y,x);
        }else{
            root.put(x,y);
        }
    }
}
class Node{
    int x;
    int y;

    Node(int x,int y){
        this.x = x;
        this.y = y;
    }
}