• 개인 공부 목적으로 작성한 포스팅입니다.
  • 아래 출처를 참고하여 작성하였습니다. :)

문제: 내 선물을 받아줘

  • 그래프 내에 존재하는 싸이클 갯수가 정답이 됩니다.
  • 그리고 맨 처음 접근한 방식은 BFS로 전체 노드를 방문할 때 몇 개의 컴포넌트로 나뉘는지로 구할 수 있다고 생각했습니다.

BFS 방문 컴포넌트 갯수 != 싸이클 갯수

  • 이 방식은 정답이 아닙니다.
  • 왜냐면 싸이클 루프에 포함되지는 않지만 싸이클에 진입하는 외부 노드의 경우 문제가 됩니다.
  • 싸이클에 진입하는 외부 노드의 BFS 호출이 싸이클 루프의 BFS 호출보다 나중에 이뤄진다면, 외부 노드는 방문하지 않았으므로 BFS 방문 컴포넌트 갯수를 증가시키게 됩니다.
  • 그러나 싸이클 입장에서는 싸이클에 포함되는 노드이므로 새로운 컴포넌트로 추가되면 안됩니다.
  • 이런 이유로 싸이클 갯수를 세려고 할 때 BFS 방문 컴포넌트 갯수로 세면 안 됩니다.

방향 그래프에서의 싸이클 판별

  • DFS + int[] visit 조합으로 판별할 수 있습니다.
    • boolean[]이 아니라 굳이 int[] visit가 필요한 이유는 세 가지 상태를 갖는 방문배열이 필요하기 때문입니다.
//visit[here] == -1 : 현재 DFS(here)이 실행 중이다.
//visit[here] == 1 : DFS(here)은 이미 탐색이 완료된 상태이다.(싸이클과 관련없는 정점으로 판명난 상태)
//visit[here] == 0 : here은 아직 방문하지 않은 정점이다.
int[] visit;

boolean hasCycle(int here) {
    if (visit[here] != 0) { //이미 방문 했었던 정점에 도착
        return visit[here] == -1; //DFS가 끝나기 전에 또 들린거라면 사이클 존재.
    }
    //여기에 왔다는건 here에서 처음 DFS를 돌린다는 뜻이다.
    visit[here] = -1;
    for (int nxt : adj[here]) {
        if (hasCycle(nxt)) return true; //하나라도 true면 사이클 존재
    }
    visit[here] = 1; //here에서의 DFS가 전부 끝났다.
    return false;
}

정답 코드

해결한 방식은 아래와 같습니다.

  • 현재 노드를 DFS 호출했는데 이미 DFS가 진행중인 노드였다면 싸이클을 형성한 것이므로 싸이클이라는 걸 표시하고 리턴시킵니다.
  • 현재 노드를 DFS 호출했는데 이미 이전 DFS로 탐색이 끝난 노드였다면 싸이클과 무관한 정상 케이스이므로 정상 케이스라는 걸 표시하고 리턴시킵니다.
  • 현재 노드를 DFS 호출했는데 아직 한 번도 방문 안 한 노드였다면 이제 방문을 시작하므로 현재 노드에 DFS 진행중이라고 표시를 하고 다음 노드를 방문하러 갑니다.
  • 현재 노드 방문이 끝나면 방문 완료 표시를 꼭 해줘야하며, 자신의 다음 노드들 중에 싸이클이 존재한다면 자신도 싸이클에 포함되므로 싸이클 여부를 메서드 리턴 value로 줍니다.
import java.io.*;
import java.util.*;

public class Main {

    static final int NORTH = 0;
    static final int SOUTH = 1;
    static final int WEST = 2;
    static final int EAST = 3;

    static final int NOT_VISIT = 0;
    static final int VISITNG = 1;
    static final int DONE = 2;

    static final int NOT_CYCLE = 0;
    static final int CYCLE = 1;

    static final int[] dy = {-1, 1, 0, 0};
    static final int[] dx = {0, 0, -1, 1};
    static int N, M;
    static int[][] visit;
    static int[][] board;

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

        String[] nmInfo = br.readLine().split(" ");
        N = Integer.parseInt(nmInfo[0]);
        M = Integer.parseInt(nmInfo[1]);

        visit = new int[N][M];
        board = new int[N][M];

        for (int i = 0; i < N; ++i) {
            String row = br.readLine();

            for (int j = 0; j < row.length(); ++j) {
                char c = row.charAt(j);
                if (c == 'N') {
                    board[i][j] = NORTH;
                } else if (c == 'S') {
                    board[i][j] = SOUTH;
                } else if (c == 'W') {
                    board[i][j] = WEST;
                } else {
                    board[i][j] = EAST;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (visit[i][j] == NOT_VISIT) {
                    ans += dfs(i, j);
                }
            }
        }

        System.out.println(ans);
    }

    static int dfs(int y, int x) {
        if (visit[y][x] == VISITNG) {
            return CYCLE;
        } else if (visit[y][x] == DONE) {
            return NOT_CYCLE;
        }

        visit[y][x] = VISITNG;

        int dir = board[y][x];
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        int result = dfs(ny, nx);

        visit[y][x] = DONE;

        return result;
    }
}