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

문제

그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다.
길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다.
다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지 알아내는 프로그램을 작성하여라.

• A와 B는 숫자 0과 99으로 고정된다.
• 모든 길은 순서쌍으로 나타내어진다. 위 예시에서 2번에서 출발 할 수 있는 길의 표현은 (2, 5), (2, 9)로 나타낼 수 있다.
• 가는 길의 개수와 상관없이 한가지 길이라도 존재한다면 길이 존재하는 것이다.
• 단 화살표 방향을 거슬러 돌아갈 수는 없다.

[제약 사항]
출발점은 0, 도착점은 99으로 표현된다.
정점(분기점)의 개수는 98개(출발점과 도착점 제외)를 넘어가지 않으며, 한 개의 정점에서 선택할 수 있는 길의 개수도 2개를 넘어가지 않는다.
아래 제시된 가이드 라인은 제안사항일 뿐 강제사항은 아니다.

[데이터 저장 가이드]
정점(분기점)의 개수가 최대 100개 이기 때문에, size [100]의 정적 배열 2개을 선언하여, 각 정점의 번호를 주소로 사용하고, 저장되는 데이터는 각 정점에서 도착하는 정점의 번호를 저장한다.
위 그림을 저장하였을 때 결과는 다음과 같다.

입력

총 10개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호와 길의 총 개수가 공백으로 분리되어 주어진다.
그 다음 줄에는 순서쌍이 주어진다. 순서쌍의 경우, 별도로 나누어 표현되는 것이 아니라 숫자의 나열이며, 나열된 순서대로 순서쌍을 이룬다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답(가능 여부)을 출력한다.
가능할 경우 1, 불가능할 경우 0을 출력한다.

예제 입력

1 16
0 1 0 2 1 4 1 3 4 8 4 3 2 9 2 5 5 6 5 7 7 99 7 9 9 8 9 10 6 10 3 7

예제 출력

#1 1

코드

package live08._02_길찾기;

import java.util.*;
import java.io.*;

public class Solution {
	static boolean[][] graph;
	static boolean[] visited;
	static int tcNum, wayNum;

	static void dfs(int idx) {
		if (visited[99]) {
			return;
		}
		visited[idx] = true;
		for (int i = 0; i < 100; i++) {
			if (!visited[i] && graph[idx][i]) {
				dfs(i);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src/live08/_02_길찾기/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int T = 10;

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			tcNum = Integer.parseInt(st.nextToken());
			wayNum = Integer.parseInt(st.nextToken());

			graph = new boolean[100][100];
			visited = new boolean[100];

			st = new StringTokenizer(br.readLine());

			for (int i = 0; i < wayNum; i++) {
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());

				graph[x][y] = true;
			}

			dfs(0);

			bw.write("#" + tcNum + " " + (visited[99] ? 1 : 0) + "\n");

		}

		bw.close();
		br.close();
	}
}

풀이

• 이전에 풀었던 정석적인 DFS 구현이 크게 달라진점이 없다.
• 다만, 이번에는 100 × 100 짜리 2차원 배열을 사용하고, 반복문이 최대 100번 반복하게 된다.
• 그래서 dfs 함수 내부에 조건 만족 시 dfs를 종료하는 return; 을 추가했다.
• 정점들을 방문하면서 방문 여부를 visited[idx] = true;로 기록하고,
• 99번 정점을 방문했을 때 1을 출력하고, 모든 정점을 방문해도 99번 정점을 방문하지 못하였을 때 0을 출력한다.

어려웠던 점

• 연결 정보를 저장하는 것이 어려웠다.
• 순서쌍 개수를 알려주고, 순서쌍 정보를 한 줄로 나열하였기 때문에
• 두 개씩 묶어서 값을 받는 것을 생각하기 어려웠다.
• 근데 구현하고 보니 쉬워보인다.