[SWEA] 1219. 길찾기 (Java)

문제

SW Expert Academy

 

풀이

0. 문제해석

깊이우선탐색을 이용하여

한 도시를 지날때마다 두방향으로 탐색을 해가면 도착점 도착 여부를 판별할 수 있다.

 

1. 길 입력

두가지 길이 존재하므로

이미 길이 하나 입력된 상태라면

두번째 배열에 저장해준다.

 

2. 두 방향 탐색

도시에서 계속 두방향으로 뻗어나가며

index 값을 확인하여 0 이라면 더이상 길이 없다는 것이고, 99라면 도착점에 도착한 것이므로 리턴해준다.

 

3. 전체코드

// [SWEA] 1219. 길찾기 (Java)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static final int size = 100;
	static int[][] arr;
	static int result;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for(int test = 1; test <= 10; test++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int t = Integer.parseInt(st.nextToken()); // 테스트 케이스 번호
			int n = Integer.parseInt(st.nextToken()); // 길의 총 개수
			
			arr = new int[size][2];
			result = 0;
			
			// 순서쌍 입력
			st = new StringTokenizer(br.readLine());
			for(int i = 0; i < n; i++) {
				int index = Integer.parseInt(st.nextToken()); // 순서쌍 인덱스
				int value = Integer.parseInt(st.nextToken()); // 순서쌍 값
				
				// 이미 길이 하나 있다면 두번째 배열에 저장
				if(arr[index][0] != 0) {
					arr[index][1] = value;
				} else {
					arr[index][0] = value;
				}				
			}
			
			// 두 방향 탐색 시작
			solve(arr[0][0]);
			solve(arr[0][1]);
			
			System.out.println("#" + t + " " + result);
		}
		br.close();
	}
	
	public static void solve(int index) {
		
		// 더이상 길이 없다면
		if(index == 0) {
			return;
		}
		
		// 도착점에 도착했다면
		if(index == 99) {
			result = 1;
			return;
		}	
		
		// 두 방향 탐색
		solve(arr[index][0]);
		solve(arr[index][1]);
	}
}