[SWEA] 1219. [S/W 문제해결 기본] 4일차 - 길찾기

문제

그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다.

길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다.

다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지 알아내는 프로그램을 작성하여라.

 - A와 B는 숫자 0과 99으로 고정된다.

 - 모든 길은 순서쌍으로 나타내어진다. 위 예시에서 2번에서 출발 할 수 있는 길의 표현은 (2, 5), (2, 9)로 나타낼 수 있다.

 - 가는 길의 개수와 상관없이 한가지 길이라도 존재한다면 길이 존재하는 것이다.

 - 단 화살표 방향을 거슬러 돌아갈 수는 없다.

 

 

풀이방법

DFS(깊이 우선 탐색)을 이용해 문제 해결.

 

입력에 따라 각 노드와 간선을 나타내는 인접행렬을 만들고, 0노드에서 출발해 99번째 노드로 갈 수 있는 경로가 존재하는지 찾는다.

 

소스코드

package samsung;

import java.util.*;

public class s_1219 {
	static int[][] a;
	static int[] v;
	static int find;
	
	public static void dfs(int x) {
		if(find == 1)
			return;
		if(x == 99) {
			find = 1;
			return;
		}
		v[x] = 1;
		for(int i = 0; i < 100; i++) {
			if(v[i] == 0 && a[x][i] == 1)
				dfs(i);
		}
		v[x] = 0;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for(int t = 1; t <= 10; t++) {
			int tc = sc.nextInt();
			int n = sc.nextInt();
			a = new int[100][100];
			v = new int[100];
			find = 0;
			for(int i = 0; i < n; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				a[x][y] = 1;
			}
			
			dfs(0);
			System.out.println("#" + t + " " + find);
		}
	}
}