[BaekJoon] 15886번 내 선물을 받아줘2 (Java) 문제 풀이 [Silver 3]

문제

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

15886번: 내 선물을 받아줘 2

 

어떻게 풀 것인가?

문제의 접근은 DFS가 맞다.

다만, 특정위치가 주어지지 않고 주어진 행렬에서 DFS 검사를 모두 행해야하며, 그에 따라 visit 배열도 그 때마다 생성을 해준다.

 

문제의 예제를 통해서 살펴보자.

 

===> 첫 번째 길 찾기

E E W W E W

1 1 1

 

===> 두 번째 길 찾기

E E W W E W

1 1 1 2

2번 길은 1번 길과 연결되어 결국 1번으로 길에 포함이 된다.

1 1 1 1

 

===> 세 번째 길 찾기

E E W W E W

1 1 1 1 3 3

 

마지막으로,

길 개수를 세어주면 된다.

 

DFS 알고리즘을 이용해서 반복되는 경로를 구하고 HashSet으로 중복된 경로를 구분해 선물을 놓을 장소의 수를 구했다.

 

풀면서 놓쳤던점

처음에 아이디어를 떠올리기 어려웠다. 하지만, 연습하면 될 것 같다는 생각이 들었다.

 

이 문제를 통해 얻어갈 것

DFS 활용.

 

내 코드 

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

// 백준알고리즘 15886번 내 선물을 받아줘2
public class Main {
    static boolean[] visit;
    static int N;

    static String str;
    static HashSet<Integer> set = new HashSet<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        str = br.readLine();

        for (int i = 0; i < N; i++) {
            visit = new boolean[N];
            DFS(i);
        }
        System.out.println(set.size());
    }

    static void DFS(int x) {
        if (set.contains(x)) return;
        if (visit[x]) {
            set.add(x);
            return;
        }

        visit[x] = true;
        if (str.charAt(x) == 'W') {
            DFS(x - 1);

        }
        if (str.charAt(x) == 'E') {
            DFS(x + 1);

        }
    }
}

 

참고

X