[ 백준 ] 16724 피리 부는 사나이

Link | 백준 16724번 문제 : 피리 부는 사나이

📌 About

DFS으로 간단히 처리할 수 있는 문제이다.

하지만 DFS 내부의 탐색 과정을 구현하는 방법을 고려해야 한다.

우선 map은 U, R, D, L 이외에도 O, X를 추가한다.

X는 현재 DFS에서 탐색한 부분이다. (안전구역 설치 탐색 영역)

O는 이전 DFS에서 탐색 완료한 부분이다. (안전구역 설치 완료 영역)

DFS 탐색을 하다가 현재 DFS에서 탐색한 영역(X)에 도달하면 새로운 안전구역을 설치한다.

반면에 이미 안전 구역에 도달하게 되는 영역(O)에 도달하면 현재 탐색한 영역은 이미 안전하다.

다음의 예시를 보자.

탐색은 왼쪽 위부터 우측 방향으로 진행한다.

영역은 다음과 같이 표시한다. (ROW, COL, TYPE)

(0, 0, D)은 미탐색 영역이기 때문에 DFS를 한다.

여기서 이해를 위해 X는 노란색으로 O는 파란색으로 표시한다.

결과적으로 탐색은 현재 DFS으로 탐색한 (0, 0, D)에 도달한다.

때문에 새로운 안전 구역 설치가 필요하며 노란색 영역은 안전해진다.

이미 안전해진 영역(O)는 DFS 탐색을 하지 않아도 되므로 다음 탐색은 (0, 2, R)이다.

이번 탐색은 결과적으로 파란색 영역에 도달한다.

즉, 파란색 영역에 설치되어 있는 안전구역 때문에 노란색 영역도 안전해진다.

추가로 안전구역을 설치할 필요가 없는 것이다.

마지막으로 (1, 2, R)에서 DFS를 한다.

이번 탐색 또한 결과적으로 파란색 영역에 도달하기 때문에 추가 안전구역 설치가 필요 없다.

결과적으로 모든 영역이 안전해지기 위해서는 하나의 안전구역만 설치해도 된다.

또 다른 예는 다음과 같다.

📌 Solution

Step 1. 주어진 입력에 맞게 배열을 생성한다.

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int R = Integer.parseInt(tokenizer.nextToken());
int C = Integer.parseInt(tokenizer.nextToken());

map = new char[R][C];
for (int r = 0; r < R; r++) map[r] = reader.readLine().toCharArray();

Step 2. 탐색을 시작할 영역을 찾는다.

이미 탐색한 영역은 넘어간다.

int count = 0;
for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
        if (map[r][c] != 'O' && search(r, c)) count++;

Step 3. O나 X 영역을 만날때까지 탐색한다.

private boolean search(int r, int c) {
    char type = map[r][c];
    map[r][c] = 'X';

    boolean flag;
    if (type == 'X') flag = true;
    else if (type == 'O') flag = false;
    else if (type == 'U') flag = search(r - 1, c);
    else if (type == 'R') flag = search(r, c + 1);
    else if (type == 'D') flag = search(r + 1, c);
    else flag = search(r, c - 1);

    map[r][c] = 'O';
    return flag;
}

📌 Code

GitHub Repository

char[][] map;

public void solve() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int R = Integer.parseInt(tokenizer.nextToken());
    int C = Integer.parseInt(tokenizer.nextToken());

    map = new char[R][C];
    for (int r = 0; r < R; r++) map[r] = reader.readLine().toCharArray();

    int count = 0;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (map[r][c] != 'O' && search(r, c)) count++;

    result.append(count);
}

private boolean search(int r, int c) {
    char type = map[r][c];
    map[r][c] = 'X';

    boolean flag;
    if (type == 'X') flag = true;
    else if (type == 'O') flag = false;
    else if (type == 'U') flag = search(r - 1, c);
    else if (type == 'R') flag = search(r, c + 1);
    else if (type == 'D') flag = search(r + 1, c);
    else flag = search(r, c - 1);

    map[r][c] = 'O';
    return flag;
}