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

길찾기

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

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

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

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

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

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

---

풀이

배열을 2개 생성한 후 입력을 받을 때 이미 배열1에 값이 있다면 배열2에 저장하도록 구현한다.

배열 각각에 현재 번호에서 갈 수 있는 곳이 있다면 재귀를 통해 진행할 수 있도록 한다.

현재 번호가 99라면 ans의 값을 1로 바꿔준다.

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

public class Solution {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for(int tc = 1; tc <= 10; tc++ ) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int cnt = Integer.parseInt(st.nextToken());
			
			int[] road1 = new int[100];
			int[] road2 = new int[100];
			
			st = new StringTokenizer(br.readLine(), " ");
			
			for(int i = 0; i < cnt; i++) {
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				
				if(road1[start] != 0) {
					road2[start] = end;
				}else {
					road1[start] = end;
				}
			}
			
			ans = 0;
			move(road1, road2, 0);
			System.out.println("#"+tc+" "+ans);
			
		}

	}
	
	static int ans;
	static void move(int[] road1, int[] road2, int now) {
		if(now == 99) {
			ans = 1;
			return;
		}
		
		if(road1[now] != 0) {
			move(road1, road2, road1[now]);
		}
		if(road2[now] != 0) {
			move(road1, road2, road2[now]);
		}
		
	}

}