Yong's Tech Story

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

문제 풀이 (JAVA) 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static List<ArrayList<Integer>> graph = new ArrayList<>(); // 인접 그래프 리스트
	static int[][] arr; // 이차열 배열 변수
	static boolean[] visited; // 방문 여부 배열 변수
	static int N;

	public static void main(String[] args) throws IOException {
		// 경로 찾기(그래프 탐색)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st;

		N = Integer.parseInt(br.readLine());

		arr = new int[N + 1][N + 1];

		for (int i = 0; i <= N; i++) {
        	// 인접 그래프 리스트 생성자 추가
			graph.add(new ArrayList<>());
		}

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				int num = Integer.parseInt(st.nextToken());
				if (num == 1) {
					graph.get(i).add(j); // 인접 그래프 리스트 요소 추가(a->b 간선)
				}
			}
		}
		
        // 1부터 N까지 경로 dfs 반복하여 탐색
		for (int i = 1; i <= N; i++) {
			visited = new boolean[N + 1];
			dfs(i, i);
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				System.out.print(arr[i][j] + " ");

			}
			System.out.println();
		}
	}

	private static void dfs(int n, int start) {
		for (Integer next : graph.get(n)) {
			if (visited[next] == false) {
				visited[next] = true;
				arr[start][next] = 1; // 1부터 ~ N까지 start를 저장하여 dfs 배열에 저장
				dfs(next, start);
			}
		}
	}

}

문제 풀이

1. 경로를 탐색하는 문제로 다양한 방법이 있지만 DFS를 사용

2. 처음에는 dfs함수의 visited=true -> dfs -> visited=false로 하였지만, 시간 초과 발생

3. visited를 false로 할 필요가 없는 이유는 start 노드에서 N까지 갈 수 있는지만 보면 되기 때문에 모든 경우의 N을 구할 필요가 없기 때문이다.

4. 따라서 1~N까지 start 노드를 넘겨 dfs가 돌면서 방문하였을때, 연결이 된 노드로 dfs가 끝나면 간선간의 연결 여부를 알 수 있다.

결론

: 문제의 접근을 모든 경우의 수 가 아닌 1~N까지의 숫자가 다른 숫자 노드와 연결 되는지 여부를 생각하여 접근한다면 쉬웠을 것이다. 다양한 경우의 경로 탐색 문제를 많이 풀어봐야겠다는 생각을 하였다.