[백준]15559번 내 선물을 받아줘(java)

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

15559번: 내 선물을 받아줘

dfs 문제이다.

 

핵심

아래 알파벳에 따라 이동하는 길이 정해져 있고, 맵의 크기를 넘어서지 않는다.

즉 무조건 사이클이 생기게 된다. 이때 생기는 사이클의 수를 구하면 된다.

사이클을 구분하기 위해 depth를 증가시키면 탐색한다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static char[][] map;
    static int[][] visited;
    static int result;
    static int depth;
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] info = br.readLine().split(" ");
        int n = Integer.parseInt(info[0]);
        int m = Integer.parseInt(info[1]);
        map = new char[n][m];
        visited = new int[n][m];

        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++){
                if (visited[i][j] == 0){
                    depth++;
                    dfs(i,j);
                }
            }
        }
        System.out.println(result);
    }

    public static void dfs(int y, int x){
        visited[y][x] = depth;

        char c = map[y][x];
        int[] next = new int[2];
        if (c=='N')next[0] = -1;
        else if (c == 'E') next[1] = 1;
        else if (c == 'S') next[0] = 1;
        else next[1] = -1;

        int moveY = y + next[0];
        int moveX = x + next[1];

        if (visited[moveY][moveX] == 0){
            dfs(moveY,moveX);
        } else if (visited[moveY][moveX] == depth) {
            result++;
        }
    }
}

해설

우선 입력값을 받아 map을 만든다.

이후 아직 방문하지 않은 곳을 탐색하는데, 탐색할 때마다 다른 depth를 가지고 탐색하게 된다.

만약 다음 위치가 방문하지 않은 곳이라면 같은 depth를 입력한다.

만약 이미 방문한 곳이라면 나와 같은 depth인지 확인한다. 같은 depth의 경우 사이클을 의미한다.

 

 

배운 점

문제를 분석하는 것을 잘한다면 이 문제가 그리 어렵지 않을 것이다.

난이도가 어려워질수록 구현이 단순하더라도 논리를 잘 세워야 하는 경우가 많은 것 같다.

많이 풀고 많이 생각하자.