[Java] SWEA 1219번 길찾기

SW Expert Academy

---

풀이

edge1과 edge2를 가거나 안가는 경우를 전부 할 수 있도록 부분집합을 이용해서 해결했습니다.

싸이클은 고려안했는데도 테스트케이스가 다 맞아서 혹시 하고 제출했는데 패스가 되어서 당황했던 문제입니다.

---

코드

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

public class Solution {
	public static int N, answer;
	public static int[] edge1, edge2;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		StringTokenizer st;
		
		for (int tc = 1; tc <= 10; ++tc) {
			st = new StringTokenizer(br.readLine());
			st.nextToken();
			N = Integer.parseInt(st.nextToken());
			
			edge1 = new int[100];
			edge2 = new int[100];
			
			for (int i = 0; i < 100; ++i) {
				edge1[i] = -1;
				edge2[i] = -1;
			}
			
			answer = 0;
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; ++i) {
				int idx = Integer.parseInt(st.nextToken());
				int val = Integer.parseInt(st.nextToken());
				if (edge1[idx] > 0) {
					edge2[idx] = val;
				}
				else {
					edge1[idx] = val;
				}
			}
			
			go(0);
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		
		System.out.println(sb);
	}
	
	public static void go(int val) {
		if (val == -1) {
			return;
		}
		
		if (val == 99) {
			answer = 1;
			return;
		}
		
		if (answer == 1) {
			return;
		}
		
		go(edge1[val]);
		go(edge2[val]);
	}
}

---

pyo7410/Algorithm