[JAVA] SWEA 1219번 길찾기

문제

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

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

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

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

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

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

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

 

제약 사항

출발점은 0, 도착점은 99으로 표현된다.

정점(분기점)의 개수는 98개(출발점과 도착점 제외)를 넘어가지 않으며, 한 개의 정점에서 선택할 수 있는 길의 개수도 2개를 넘어가지 않는다.

아래 제시된 가이드 라인은 제안사항일 뿐 강제사항은 아니다.

입력

각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호와 길의 총 개수가 주어지고 그 다음 줄에는 순서쌍이 주어진다.

순서쌍의 경우, 별도로 나누어 표현되는 것이 아니라 숫자의 나열이며, 나열된 순서대로 순서쌍을 이룬다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

풀이

stack과 DFS를 합쳐 풀이하였다.

 

입력을 두개씩 받아 2차원 배열의 해당 위치에 값을 저장하고, stack 배열의 top 자리에 값을 추가하며 DFS를 수행한다.

 

도착한 해당 값에 대해 visited 배열에 true를 저장해 길에 방문했음을 알린다.

 

DFS를 돌며 99를 만나면 길이 있음을 알리고, 연산을 중단하고 값을 출력한다.

 

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

public class 길찾기 {
	static boolean [] visited;
	static int[][] map;
	static StringTokenizer st;
	static int start, end;
	static int [] stack;
	static int top;
	static boolean isWay;
	
	public static boolean DFS(int start) {
		while (top != -1) {
			boolean flag = false;
			for (int i = 0; i < map.length; i++) {
				if (map[start][i] == 1 && visited[i] == false) {
					if (i == 99) {isWay = true; break;}
					stack[++top] = i;
					visited[i] = true;
					flag = true;
					DFS(i);
				}
			}
			if (!flag) break;
			top--;
		}
		return isWay;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for (int test_case = 1; test_case <= 10; test_case++) {
			st = new StringTokenizer(br.readLine(), " ");
			int tc = Integer.parseInt(st.nextToken());
			int ways = Integer.parseInt(st.nextToken());
			
			map = new int[100][100];
			visited = new boolean[100];
			
			stack = new int[10000];
			top = -1;
			isWay = false;
			
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < ways; i++) {
				start = Integer.parseInt(st.nextToken());
				end = Integer.parseInt(st.nextToken());
				
				map[start][end] = 1;
			}
			
			stack[++top] = 0;
			visited[0] = true;
			
			System.out.println("#" + test_case + " " + (DFS(0) ? 1 : 0));
		}
		
		
	}
}