[백준 21736번] 헌내기는 친구가 필요해 - JAVA

문제 링크

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색을 통해 풀이할 수 있는 문제이다.

 

접근 방법

문제 설명에 나와있듯 주어진 위치에서 위, 아래, 좌, 우로 배열을 탐색해 타겟 찾고, 그 수만큼 카운트한다.

조건

• 벽(‘X’)으로 둘러 쌓인 곳은 접근할 수 없고, 배열의 크기를 벗어난 범위 역시 마찬가지이다.
• 타겟(‘P’)를 발견하더라도 더 탐색할 수 있다면 종료하지 않고 계속해서 탐색한다.
• 만약 탐색이 종료되었고, 타겟을 찾은 개 수가 0이라면 'TT’를 출력한다.

DFS 혹은 BFS는 기본적으로 배열을 탐색할 때 무한 루프에 빠지지 않기 위해 방문 여부를 확인해야 할 필요가 있다.

 

 

추가로 이번 문제에선 시작 지점이 주어져 있으므로 탐색 배열을 채워 나갈 때 해당 위치를 미리 저장하고, 첫 번째 루프에 이용한다.

 

 

여기까지 준비가 되었다면 이제 DFS로 새 친구를 찾아보자

---

풀이

[BufferedReader + DFS]를 사용해 풀이한다.

package backjun;

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

public class NewFriend {

    // 이차원 배열 탐색을 위한 dx, dy 배열
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int n;
    static int m;

    // 탐색 배열
    static char[][] arr;
    // 방문 여부 확인
    static boolean[][] check;

    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);

        arr = new char[n][m];
        check = new boolean[n][m];

        int doyeonX = 0;
        int doyeonY = 0;

        for (int i = 0; i < arr.length; i++) {
            char[] data = br.readLine().toCharArray();
            for (int j = 0; j < arr[i].length; j++) {
                // 시작 위치 저장
                if (data[j] == 'I') {
                    doyeonX = i;
                    doyeonY = j;
                }
                // 탐색 배열 저장
                arr[i][j] = data[j];
            }
        }

        findBuddy(doyeonX, doyeonY);

        if (cnt == 0) {
            System.out.println("TT");
        } else {
            System.out.println(cnt);
        }
    }

    private static void findBuddy(int x, int y) {
        check[x][y] = true;
        if (arr[x][y] == 'P') {
            cnt++;
        }
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (isValid(nx, ny) && !check[nx][ny] && arr[nx][ny] != 'X') {
                findBuddy(nx, ny);
            }
        }
    }

    private static boolean isValid(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
}

기본적인 DFS는 if - else 문으로 원하는 조건이 아닐 경우 동작하는 방식이지만, 이 문제에서 원하는 것은 타겟 -> 'P'를 발견한 후에도 다음 위치로 이동하여 또 다른 친구를 찾는 것을 원하기 때문에 if - else로 묶을 경우 풀이에 실패한다.

 

---