BOJ 11403번 경로찾기

오늘의 주제

오늘의 주제는 백준 알고리즘 11403번 경로찾기 입니다. 경로찾기는 방향 그래프 탐색에 관한 문제입니다.

저는 깊이 우선 탐색(DFS)를 통해서 문제를 해결했지만,  너비 우선 탐색 및 워셜 알고리즘을 통해서도 해결이 가능합니다. 우선 문제를 살펴보도록 하죠

가중치 없는 방향 그래프가 방문할 수 있는 모든 정점을 찾아 행렬로 표시하는 문제입니다.

테스트 데이터는 다음과 같습니다.

예제 입력1의 인접행렬의 경우 문제를 해결하기 위해 각 정점(편하게 A,B,C)을 시작점으로 잡을 수 있습니다.

정점 A를 시작점으로 잡을 경우는  A->B->C->A

정점 B를 시작점으로 잡을 경우는  B->C->A->B

정점 C를 시작점으로 잡을 경우는 C->A->B->A

위와 같이 총 3가지의 순환 구조를 갖습니다. 각각의 정점을 시작점으로 찾고 그래프를 순회할 경우 아래와 같은 결과가 도출 됩니다.

이 문제를 해결할 때 주의해야 할 점은 탐색시 마지막 노드에서 깊이 우선 탐색을 진행할 때 시작점과 순환구조를 가질 수 있다는 점에 주의 해야합니다.

기본적인 탐색문제에서 약간만 변형하면 쉽게 해결 할 수 있는 문제였던거 같습니다.

package algo;

import java.util.Scanner;
import java.util.Stack;

// 1. 문제 자체는 어처피 완전탐색을 목표로 하는 문제
// 공부하는 의미로 푸는 것이기 때문에, bfs & dfs로 전부 코딩해보기

public class boj_11403 {
    static int[][] map;

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt();

        int[][] ad = new int[size][size];
        int[] c;
        map = new int[size][size];

        for(int i = 0; i < size; ++i) {
            for(int j = 0; j < size; ++j) {
                ad[i][j] = sc.nextInt();
                map[i][j] = ad[i][j];
            }
        }

        for(int i = 0; i < size; ++i) {
            c = new int[size];
            dfs(ad, c, i);
        }
        for(int i = 0; i < size; ++i) {
            for(int j = 0; j < size; ++j) {
                System.out.print(map[i][j]+ " ");
            }
            System.out.println();
        }
    }


    static void dfs(int[][] ad, int[] c, int start) {

        // dfs는 깊이 우선 탐색, 깊이를 우선으로 탐색하기 때문에 스택을 이용한다.
        // 방문 배열의 경우 0인 경우 미방문, 1인 경우 방문
        Stack s = new Stack<>();
        s.push(start);
        int n = ad.length;

        while(!s.isEmpty()) {
            int v = s.peek(); // 스택 최상단 원소를 꺼내온다.
            boolean flag = false;
            for(int i = 0; i < n; ++i) {
                if(ad[v][i] == 1 && c[i] == 0) {
                    s.push(i);
                    map[start][i] = 1;
                    c[i] = 1;
                    flag = true;

                    break;
                }
            }
            if(!flag) {
                s.pop();
            }
        }
    }
}