[백준][C++] 16724번: 피리 부는 사나이 <229>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

16724번: 피리 부는 사나이

 

생각의 흐름

우선 이 문제를 보고 생각한 방식은 cycle을 찾는 방식이였다.

우리 문제의 예시 를 생각해보자!

 

3 4
DLLL
DRLU
RRRU

우선 맨 왼쪽 위 부터 탐색을 시작한다고 해보자

맨 처음 모든 칸의 findSafe[][]값은 -1로 초기화 되어있다. 방문한적 없음을 의미한다.

(0,0)지점은 지금 방문했기 때문에 res값인 1을 담아둔다.

이후 다음 이동 지점의 알파벳을 따라서 방향을 진행하다 보면 다음과 같은 순간이 온다.

(0,1) 에서 이전에 방문했었던 (0,0) 에 다시 접근하려 할때 해당 (0,0)칸의 findSafe[][]의 값은 1이다.

따라서 이전에 방문했었던적이 있다는 의미이다.

 

이때 그냥 다음과 같이 (0,0)의 findSafe의 값을 바로 반환시켜버리면 된다.

if(findSafe[x][y] != -1) {
    return findSafe[x][y];
}

이렇게 하면 BFS를 호출했던 역순으로 되돌아 올라가면서 해당 칸의 findSafe값을 직전 함수의 호출로 전달하는 것 이다.

따라서 탐색 이후의 findSafe의 값들은 다음과 같다.

해당 칸에 findSafe 값들이 적혀있다.

 

하지만 아래 코드를 보면 의문이 들수도 있다. DFS의 큰 틀은 다음과 같은데...

int DFS(int x, int y) {
    if(findSafe[x][y] != -1) {
        return findSafe[x][y];
    }

    findSafe[x][y] = res;  // 직전에 값을 대입
    // 생략...

    int nx = x + dx[dir];
    int ny = y + dy[dir];
    findSafe[x][y] = DFS(nx, ny);  // 호출 이후에도 대입
    return findSafe[x][y];
}

호출 직전에는 왜 값을 대입할까? DFS의 호출후 반환값만 findSafe에 대입해주면 되는 것 아닐까?

cycle을 찾으면 해당 시점에 백트래킹을 하면서 findSafe값을 채워주면 될거라는 생각이였다.

하지만 호출 전에도 값을 채우는 이유가 있었다.

 

만약 다음과 같이 그레프가 있었다고 해보자.

원래 L이였던 칸이 R로 바꾼 상태이다.

2번째 탐색이기 때문에 res++ 을 진행해준다.

 

이러면 2번째 탐색을 (1,1)을 에서 시작할때 (1,1) -> (1,2) -> (1,3)으로 이동하는데 

직전 대입때는 findSafe에 2를 대입(res++를 했으니)하게 되고, (1,3) 칸에 도착했을때는 BFS 반환값으로 1을 반환하게 되니 findSafe에 1을 저장하게 된다.

 

safezone이 1개만 있으면 되는 상황이기 때문에 1을 저장하는것이 정확하다.

 

하지만 원래대로 R이 아니라, L 이였다면 (1,1) -> (1,2) -> (1,1) 로 되어 2로 값이 채워지게 된다.

 

나의 코드

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define MAX 1001

int N, M;
int dx[4] = { -1,0,1,0};
int dy[4] = { 0,1,0,-1};
char MAP[MAX][MAX];
int findSafe[MAX][MAX];
int res = 1;

int DFS(int x, int y) {
    if(findSafe[x][y] != -1) {
        return findSafe[x][y];
    }

    findSafe[x][y] = res;
    int dir;
    if (MAP[x][y] == 'U') {
        dir = 0;
    } else if (MAP[x][y] == 'R') {
        dir = 1;
    } else if (MAP[x][y] == 'D') {
        dir = 2;
    }else if(MAP[x][y] == 'L') {
        dir = 3;
    }

    int nx = x + dx[dir];
    int ny = y + dy[dir];
    int ret = DFS(nx, ny);
    findSafe[x][y] = ret;
    return findSafe[x][y];
}

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

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
            findSafe[i][j] = -1;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (findSafe[i][j] == -1) {
                DFS(i, j);
                res++;
            }
        }
    }
    set<int> s;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            s.insert(findSafe[i][j]);
    cout << s.size();

    return 0;
}