출퇴근길 풀어 봄

6차 HSAT 인증평가 문제가 연습문제로 풀렸길래 한 번 풀어봤습니다.

'출퇴근길' 문제만 풀어봤는데요.

문제는 [출퇴근길] 여기에서 볼 수 있고요.

출퇴근길 해설 영상

그런데 이미 이런 좋은 해설이 있더라고요. 추론 능력(?)이 좋으시다면 저 해설만으로도 충분히 이해하실 수 있으리라 생각해요. 그런데 설명해주신 분이 너무 간단하게 넘어간 부분이 있어서 그 포인트만 한 번 얘기해볼게요. (역방향 인접리스트를 만드는 이유)

추가로 Softeer 사이트에 Algotutor 게시글 댓글로 어떤 분이 역방향을 안 써도 풀린다길래 체크해봤는데요. 덕분에 재밌는 발견을 했습니다. 그 내용도 마지막에 설명할게요. (역방향 인접리스트는 한 번만 돌면 된다.)

저는 상기 문제 내용과 해설 영상을 모두 확인했다는 전제하에 가장 궁금하실 만한 포인트만 얘기하겠습니다.

역방향 인접리스트가 필요할까?

TL;DR
Yes.

지금부터 몇가지 예를 통해 설명할게요.

Case 1

(설명을 위해 집과 회사는 번호가 아닌 S와 T로 각각 표현하겠습니다.)

직관적으로 생각하면, 문제를 풀기 위해서 S 에서 출발하여 T 까지 도착하는 경로에 포함될 수 있는 노드 를 구하고 싶을 겁니다.

(지금은 일단 출근길 (S -> T) 만 고려하겠습니다.)

그렇게 하기 위해서 S 에서 출발하는 DFS 또는 BFS 를 구현하게 될 겁니다.

하지만 어떻게 2번 노드를 제외하고 1번 노드만 그러한 노드가 될 수 있다는 것을 알 수 있을까요?

아래의 코드를 살펴봅시다. (설명을 위한 최소의 로직만을 작성했습니다.) (Java 기준으로 작성했습니다.)

// ...생략...

/*
 * n 은 노드 수를 의미한다
 * adj 는 인접리스트를 의미한다
 * S 는 출발 노드 번호이다
 * T 는 도착 노드 번호이다
 */
int commute(int n, List<Integer>[] adj, int S, int T) {

    /*
     * 우리가 궁금한 정보가 담길 배열이다
     * included[i] == true 라면 i 번 노드가 출근길에 포함될 수 있는 노드이다
     */
    boolean[] included = new boolean[n + 1];

    /*
     * 탐색에 사용되는 방문 배열이다
     */
    boolean[] visited = new boolean[n + 1];

    /*
     * 도착 노드 (T) 는 이미 방문한 노드이자, 출근길에 포함될 수 있는 노드로 확정한다
     * (아래의 isIncluded 함수 참고)
     */
    included[T] = true;
    visited[T] = true;

    /*
     * DFS 로 그래프를 탐색한다
     */
    isIncluded(S, adj, included, visited);

    // ...생략...
}

/*
 * currNo 는 현재 방문한 노드 번호이다
 * adj 는 인접리스트이다
 * included 는 이 함수를 통해 완성하고자 하는 배열이다
 * visited 는 탐색에 사용되는 방문 배열이다
 *
 * 반환값은 currNo 번 노드가 출근길에 포함될 수 있으면 true, 그렇지 않으면 false 이다
 */
boolean isIncluded(int currNo, List<Integer>[] adj, boolean[] included, boolean[] visited) {

    // currNo 번 노드에 이미 방문했다면 그 결과를 반환한다
    // 만약 currNo == T (도착 노드) 라면 탐색 시작 전 미리 방문처리해두었으므로 여기에 걸린다
    // !! 여기를 주목해주세요 !!
    if (visited[currNo]) {
        return included[currNo];
    }

    // 방문 처리
    visited[currNo] = true;

    // currNo 번 노드에 인접한 노드를 탐색한다
    for (int nextNo : adj[currNo]) {
        // 만약 그러한 인접 노드 중 출근길에 포함되는 노드가 있다면
        if (isIncluded(nextNo, adj, included, visited)) {
            // 현재 노드 또한 출근길에 포함된다
            included[currNo] = true;
        }
    }

    // 그렇게 하여 구한,
    // 현재 노드가 출근길에 포함되는지의 여부를 반환한다
    return included[currNo];
}

// ...생략...

(commute 함수를 호출해서 그래프 탐색을 하게 될텐데, 그 전에 commute 함수에 인자로 넘길 인접리스트 (adj) 를 만들어야겠죠? 인접리스트를 만드는 구현은 생략했습니다.)

commute 함수가 실행되면 그래프 탐색 후 included 배열이 완성되고 included[1] == true, included[2] == false (각각 1번 노드는 포함되고 2번 노드는 포함되지 않음을 나타냄) 라는 것을 알 수 있게 됩니다.

과연 위 로직을 통해 문제를 풀 수 있을까요?

아쉽게도 이 로직에는 문제가 있습니다.

이미 방문한 노드에 방문하면 그 노드가 아직 출근길에 포함될 수 있는지 없는지 확정할 수 없다 하더라도 확정될 때까지 기다리지 않고 그 노드를 포함되지 않는다고 판단하기 때문입니다. (// !! 여기를 주목해주세요 !! 주석 부분 참고)

위 로직의 반례는 아래의 그림과 같은 경우입니다.

Case 2

S -> 1 -> 2 -> 1 -> T

위 코드는 이렇게 출근길에 분명히 2번 노드도 포함될 수 있지만 1번 노드를 방문한 이후에만 방문 가능하기 때문에 2번 노드가 포함되지 않는다고 판단합니다.

방문한 노드를 몇 번이든 또 방문할 수 있는 것을 고려하지 않은 로직은 오답입니다.

그렇다면 어떻게 해야 Case 2 의 경우에도 문제없이 1, 2번 노드가 출근길에 포함되는지 알 수 있을까요?

바로 출발 노드에서 한 번, 도착 노드에서 한 번 탐색해보는 겁니다.

(출발 노드에서 탐색할 때는 도착 노드를 신경쓰지 않습니다. 마찬가지로 도착 노드에서 탐색할 때는 출발 노드를 신경쓰지 않습니다.)

무슨 말이냐고요?

(편의를 위해 출발 노드에서부터 탐색하는 것을 정방향 탐색, 도착 노드에서부터 탐색하는 것을 역방향 탐색 이라고 하겠습니다.)

정방향 탐색 을 통해서 다음과 같은 정보를 얻습니다.

• 출발 노드에서 각 노드로의 도달 가능 여부

역방향 탐색 을 통해서는 다음과 같은 정보를 얻습니다.

• 각 노드에서 도착 노드로의 도달 가능 여부

정방향 탐색 과 역방향 탐색 을 모두 수행한 후 그 정보를 모아서 다음과 같은 정보를 도출합니다.

• 각 노드에 대해서
  • 출발 노드에서 그 노드에 도달 가능한가
  • And 그 노드에서 도착 노드로 도달 가능한가

이는 곧, 각 노드에 대해서 출근길에 포함될 수 있는가 와 같습니다.

이 출발 노드에서 한 번, 도착 노드에서 한 번 탐색하기 로직을 코드로 작성해보겠습니다.

// ...생략...

int commute(int n, List<Integer>[] adj, List<Integer>[] adjR, int S, int T) {

    /*
     * visitable  은 정방향 탐색 결과가 담길 배열이다
     * visitableR 은 역방향 탐색 결과가 담길 배열이다
     *
     * visitable[i]  == true 라면 출발 노드에서 i 노드로 도달 가능하다
     * visitableR[i] == true 라면 i 노드에서 도착 노드로 도달 가능하다
     */
    boolean[] visitable  = new boolean[n + 1];
    boolean[] visitableR = new boolean[n + 1];

    // 정방향 탐색에서는 도착 노드에서 더이상 움직이지 않으므로 미리 방문 처리한다
    // (역방향 탐색에서는 그러한 제한이 없다)
    visitable[T] = true;

    // DFS 로 그래프를 탐색한다
    // 정방향 한 번
    visit(S, adj, visitable);
    // 역방향 한 번
    visit(T, adjR, visitableR);

    // ...생략...
}

void visit(int currNo, List<Integer>[] adj, boolean[] visited) {

    if (visited[currNo]) return;
    visited[currNo] = true;

    for (int nextNo : adj[currNo]) {
        visit(nextNo, adj, visited);
    }
}

// ...생략...

(이 역시 commute 함수를 호출해서 그래프 탐색을 하게 될텐데, 그 전에 commute 함수에 인자로 넘길 인접리스트 (adj) 와 그 역 (adjR) 을 만들어야 합니다. 그 구현은 생략했습니다.)

(Case 2 의 경우에는 원래의 인접리스트와 그 역이 같은 형태겠군요.)

commute 함수를 실행하여 정방향 탐색, 역방향 탐색 을 한 번 씩 하고 visitable[i] == true && visitableR[i] == true 를 만족하는 i 를 알아내면 됩니다.

지금까지 출근길에 대해서만 다루어봤는데요. 퇴근길도 같은 방법으로 구할 수 있습니다.

출근길에도 포함될 수 있고 퇴근길에도 포함될 수 있는 노드를 직접 찾아보세요.

역방향 탐색은 출근길과 퇴근길 중 한 번만 해도 된다?

문제의 조건을 잘 읽어보면 이 문제에서는 출근길과 퇴근길로 가능한 경로가 각각 적어도 하나 이상씩 존재하는 경우만 입력으로 주어집니다. 즉, 추가적인 조건 이 없다면 문제에서 입력으로 주어지는 모든 그래프는 S 와 T 사이를 얼마든지 왔다 갔다 할 수 있는 것이죠. 다시 말해, 그래프 자체만 봤을 때 T -> S -> T 가능 & S -> T -> S 가능 (단 문제에서는 도착 노드 에 도달하면 더이상 이동할 수 없다는 추가적인 조건 이 있었죠.)

한편, 역방향 탐색을 할 때는 출발 노드 에 도달했다고 해서 이동을 멈출 이유가 없습니다. (여기에서 말하는 출발 노드 란 출근길의 경우 S, 퇴근길의 경우 T 입니다.)

따라서 출근길에 역방향 탐색을 한 번 하면 퇴근길에 또 할 필요가 없습니다. 퇴근길 역방향 탐색 으로 얻고자 한 정보와 정확히 일치하는 정보를 출근길 역방향 탐색 으로 이미 얻었기 때문이죠. (출근길 역방향 을 택하든 퇴근길 역방향 을 택하든 상관없습니다.)

하지만 이 문제는 이러한 사실까지 파악하는 것을 요구하지 않습니다. 시간복잡도에 의미있는 차이가 없기 때문이죠.

---

재밌는 문제였는데요. 시간 나면 또 이런 문제 풀이를 해보고 싶네요.

궁금한 게 있다면 댓글 달아주세요.