백준 15886 - 내 선물을 받아줘2(자바 - 그래프)

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

15886번: 내 선물을 받아줘 2

 

* 문제 요약

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

구사과가 있는 곳은 1 x N 크기의 직사각형 지도로 나타낼 수 있으며, 1 x 1 크기의 정사각형으로 나누어져 있다.

구사과의 위치는 (1, x) 로 나타낼 수 있으며, (1, x) 는 왼쪽에서부터 x번째 칸을 의미한다.

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

욱제는 구사과의 위치를 모르기 때문에, 구사과가 이동을 시작하는 위치와 관계없이 선물을 주는 방법을 알아내려고 한다.

최소 몇 개의 칸 위에 선물을 놓으면 구사과가 항상 선물을 가져가는지 구하는 프로그램을 작성하시오.

선물이 놓여진 칸에 구사과가 이동하면 구사과는 항상 선물을 가져간다.

 

* 입력

첫째 줄에 골목길의 길이 N이 주어진다. (2 <= N <= 1,000)

둘째 줄에 길이 N짜리 구사과가 있는 곳의 지도가 주어진다.

지도에 쓰여있는대로 이동했을 때, 지도를 벗어나는 경우는 없다.

 

* 출력

첫째 줄에 최소 몇 개의 칸에 선물을 놓아야 하는지 출력한다.

 

* 예시

 

* 해결 과정

EEEE, WWWW 와 같이 한 방향으로만 가는 입력이 들어올 걱정은 하지 않아도 된다.

위와 같이 입력이 들어온다면 지도의 크기는 4로 들어오게 될 텐데

EEEE 가 입력으로 들어올 경우 처음 시작위치가 1이라고 하면 E가 4번 들어온 것으로 인해 최종적으로 위치가 5로 변하게 되는데 이는 기존에 제공된 지도의 크기 4를 넘어서는 값이 된다.

WWWW 인 경우엔 애초에 x 가 지도의 왼쪽에서부터 x번째라는 의미인데, 지도에 W만 있게되면 x 값이 음수가 되어버려서 지도의 왼쪽 끝을 벗어나게 된다.

위의 2가지 경우 모두 입력 조건에서 주어진 '지도에 쓰여 있는대로 이동했을 때, 지도를 벗어나는 경우는 없다.' 는 원칙을 위배하는 값을 출력하게 되므로 이와 같은 입력은 애초에 들어오지 않는다.

 

문자열을 탐색하다가 E가 나오고 해당 위치가 아직 탐색하지 않은 위치라면 DFS(깊이 우선탐색) 탐색을 시작한다.

dfs(int i) 메소드에서는 visited 배열에서 i번째 인덱스에 해당하는 위치의 값을 true 로 바꾸어서 해당 위치의 방문 여부를 표시해준 다음 아래의 조건문을 수행한다.

1. 만약 입력받은 문자열에서 현재 i번째 인덱스의 값이 E라면 dfs(i + 1) 을 재귀호출 하여 탐색의 깊이를 늘려준다.

즉, 앞으로 E가 탐색되면 탐색 될수록 dfs() 메소드의 재귀호출 스택이 쌓이게 될 것이다.

2. 만약 입력받은 문자열에서 현재 i번째 인덱스의 값이 w라면 재귀 호출을 종료해준다.

 

재귀호출이 종료되어 원래의 높이만큼 탐색위치가 돌아가게 되면 선물을 놓는 위치의 갯수를 나타내는 값 result 를 1 증가시켜준다.

* DFS 탐색을 하던 도중 탐색하던 깊이값이 초기화 되었을 때 result 값을 늘려주는 이유

: 구사과의 원래 위치는 정확하게 어디인지 알 수 없는 상태이다. 그러나 한쪽 방향으로 계속 이동하다가(EEEEE....) 한번 방향을 바꾸게 되면 (W 탐색) 방향을 바꿔서 이동한 위치에는 확정적으로 구사과가 존재함을 알 수 있기 때문에(E를 통해 한번 지나갔다가 W를 통해 다시 복귀함) 그 위치에 선물을 두면 구사과가 확실히 선물을 가져가게 된다.

 

* 코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    static int i = 0;
    static boolean[] visited;
    static String str;

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        str = br.readLine();
        visited = new boolean[n + 1];
        int result = 0;
        for (; i < str.length(); i++) {
            if (str.charAt(i) == 'E' && !visited[i]) {
                dfs(i);
                result++;
            }
        }
        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    // W 를 만날때 까지 dfs 탐색
    private void dfs(int i) {
        visited[i] = true;
        if (str.charAt(i) == 'E') {
            dfs(i + 1);
        } else if (str.charAt(i) == 'W') {
            return;
        }
    }
}

 

DFS 재귀호출을 통해 E가 어디까지 이어지는지 확인하고, W가 탐색되었을 경우 더 이상 깊게 탐색을 진행하지 않고 재귀 호출을 종료시킴으로서 이전의 높이로 돌아가여 다시 탐색하므로 그래프 탐색 문제(DFS) 에 해당된다.