[SWEA] 1219. 길찾기

문제

1219. [S/W 문제해결 기본] 4일차 - 길찾기
A(0)에서 B(99)로 가는 길이 존재하는지 여부 확인

풀이

• 최대 2개의 갈림길 -> 100*2 2차원배열
• 화살표 방향으로만
• DFS(깊이우선탐색)방식으로 move함수를 구현함
• isTrue : B에 도착했는지 여부를 저장하는 전역변수
  move함수에서 재귀를 호출할 때마다 isTrue여부를 확인해서 이미 B에 도착했다면 더이상 함수를 호출하지 않도록 했다.
• graph[][] != 0 여부를 확인했다. ArrayList로 했다면 길이 존재하지 않을 때 graph[i]에 아무것도 없겠지만(이걸 뭐라고 표현해야하나..) List를 사용했기 때문에 0으로 초기화되어있다. 이 문제에서 0은 A(시작점)을 의미하므로 0이 아닌 경우에만 다른 도시로 가는 길이 된다. 또한, 0으로 돌아가면 무한재귀가 된다.

자바코드

import java.util.Scanner;
import java.util.Stack;
import java.io.FileInputStream;

class Solution
{
	static int [][] graph;
	static boolean isTrue;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = 10;
		for(int test_case = 1; test_case <= T; test_case++)
		{
			graph = new int[100][2];
			isTrue = false;
			int t = sc.nextInt();
			int size = sc.nextInt();
			int start, dest;
			for (int i=0; i<size; i++) {
				start = sc.nextInt();
				dest = sc.nextInt();
				if (graph[start][0] == 0) graph[start][0] = dest;
				else graph[start][1] = dest;
			}
			
			move(0);
			
			System.out.printf("#%d %d\n", test_case, isTrue?1:0);
		}
	}
	
	static void move(int start) {
		if (graph[start][0] == 99 || graph[start][1] == 99) {
			isTrue = true;
			return;
		}
		if (!isTrue && graph[start][0] != 0) move(graph[start][0]);
		if (!isTrue && graph[start][1] != 0) move(graph[start][1]);
	}
}