Yong's Tech Story

문제 풀이 (JAVA)

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

public class part7_12 {

	static int[][] graph;
	static int[] visit;
	static int N;
	static int cnt;

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

		StringTokenizer token = new StringTokenizer(br.readLine());
		N = Integer.parseInt(token.nextToken());
		int M = Integer.parseInt(token.nextToken());

		String[] str = new String[M];

		for (int i = 0; i < M; i++) {
			str[i] = br.readLine();
		}
		bw.write(Integer.toString(solution(str, N)));
		bw.flush();
		bw.close();
	}

	private static int solution(String[] array, int N) {
		graph = new int[N + 1][N + 1];
		visit = new int[N + 1];
		for (int i = 0; i < array.length; i++) {
			String[] str = array[i].split(" ");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			graph[a][b] = 1;
		}
		visit[1] = 1;
		dfs(1);
		return cnt;
	}

	private static void dfs(int n) {
		if (n == N) {
			cnt++;
		} else {
			for (int i = 1; i < graph.length; i++) {
				if (graph[n][i] == 1 && visit[i] == 0) {
					visit[i] = 1;
					dfs(i);
					visit[i] = 0;
				}
			}

		}
	}
}

주요 핵심 포인트

1. String으로 들어오는 경로 (x1, x2) 를 graph[x1][x2]에 저장한다.

2. 모든 경로를 graph에 저장하였을시 연결점을 행과 열로 구분하여 볼 수 있다.

3. 이미 방문한 경로는 다시 방문할수 없으므로, 방문하였을시 visit[n]을 1, 방문을 종료하였을시 0으로 변경함으로써 동일한 숫자 경로를 0으로 변경한다.

4. if문에서 방문하지 visit[n] == 0 조건을 걸어줌으로써 방문하지 않은 숫자에 대해서만 탐색하도록 하는 알고리즘이다.

5. 방문을 종료하고 나서는 해당 숫자를 다시 한번 방문 하는 케이스를 고려하기 위하여 vsit[n] = 0 으로 초기화한다.

6. 구하고자 하는 N, 즉  dfs(N)이 도달하였을때에 카운트를 증가하였다.

개선해야할 사항

1.  해당 문제를 풀려고 하였으나 중간에 막혀 다른 강의 소스를 참조하게 되었다. 스택으로 풀고자 하였으나, 스택 프레임을 제대로 구현하지 못하여 정상적인 데이터를 출력하지 못하였다. 모든 케이스를 탐색하기 위하여 해당 케이스를 방문하였는지, 방문하지 않았는지를 생각하고 트리를 그려 확인하는 연습이 필요할듯 하다. dfs는 많은 연습이 필요한 알고리즘이다.