[Baekjoon/C++] 16724번 - 피리 부는 사나이

[백준] Baekjoon Online Judge

문제로 이동

 

문제

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다. 

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.

지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

 

출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

 

---

풀이

#include <iostream>
using namespace std;

int N, M;
char map[1001][1001];
int check[1001][1001];

// 방문 가능 여부 확인
bool canVisit(int y, int x) {
    return (y >= 0 && y < N) && (x >= 0 && x < M);
}

// 해당 탐색으로 방문한 칸들이 새로운 집합인가?
bool isNewGroup(int y, int x, int num) {
    if (check[y][x] == num) return true;
    if (check[y][x] != 0 && check[y][x] != num) return false;

    check[y][x] = num;

    // 상하좌우
    if (map[y][x] == 'U' && canVisit(y - 1, x)) return isNewGroup(y - 1, x, num);
    else if (map[y][x] == 'D' && canVisit(y + 1, x)) return isNewGroup(y + 1, x, num);
    else if (map[y][x] == 'L' && canVisit(y, x - 1)) return isNewGroup(y, x - 1, num);
    else if (map[y][x] == 'R' && canVisit(y, x + 1)) return isNewGroup(y, x + 1, num);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) cin >> map[i][j];
    }

    int cnt = 0;
    int num = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (check[i][j] == 0) {
                if (isNewGroup(i, j, num++)) cnt++;
            }
        }
    }

    cout << cnt << '\n';

    return 0;
}

 

// 해당 탐색으로 방문한 칸들이 새로운 집합인가?
bool isNewGroup(int y, int x, int num) {
    if (check[y][x] == num) return true;
    if (check[y][x] != 0 && check[y][x] != num) return false;

    check[y][x] = num;

    // 상하좌우
    if (map[y][x] == 'U' && canVisit(y - 1, x)) return isNewGroup(y - 1, x, num);
    else if (map[y][x] == 'D' && canVisit(y + 1, x)) return isNewGroup(y + 1, x, num);
    else if (map[y][x] == 'L' && canVisit(y, x - 1)) return isNewGroup(y, x - 1, num);
    else if (map[y][x] == 'R' && canVisit(y, x + 1)) return isNewGroup(y, x + 1, num);
}

 깊이우선탐색으로 맵의 모양에 따라 탐색하여 이번 탐색에서 새로운 집합을 발견했는지를 return하는 함수이다.

 탐색을 하다 이미 이번 탐색에 방문한 칸을 방문하게 된다면 이는 새로운 집합을 발견했음을 의미하므로 true를 return한다.

 탐색을 하다 이전 탐색에 방문했던 칸을 방문하게 된다면(이미 방문한 칸이고, num과 해당 칸의 번호가 다름) 이번 탐색에서 방문한 칸들은 이미 다른 집합에 포함된 칸이라고 볼 수 있다. 그렇기에 false를 return한다.

 

// 방문 가능 여부 확인
bool canVisit(int y, int x) {
    return (y >= 0 && y < N) && (x >= 0 && x < M);
}

 해당 좌표의 칸이 방문 가능한 칸인지 확인하는 함수이다.

 

    int cnt = 0;
    int num = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (check[i][j] == 0) {
                if (isNewGroup(i, j, num++)) cnt++;
            }
        }
    }

    cout << cnt << '\n';

 main함수에서 ‘SAFE ZONE’의 수를 세는 부분의 코드이다. 각 집합은 사이클을 이루기에  ‘SAFE ZONE’ 의 최소 개수는 집합의 수와 같다.