[SWEA] #1219 - 길찾기

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD 

SW Expert Academy

 

💡 문제

---

[설명]

그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다.

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

 

[제약 사항]

1. 출발점은 0, 도착점은 99로 표현된다.

2. 정점(분기점)의 개수는 98개(출발점과 도착점 제외)를 넘어가지 않으며, 한 개의 정점에서 선택할 수 있는 길의 개수도 2개를 넘어가지 않는다.

 

💡 아이디어

---

가장 기초적인 DFS 문제라고 볼 수 있다. (BFS로 풀어도 무관)

먼저, 두 접점의 연결을 표현하기 위해 인접 행렬(Adjacency Matrix)로 나타낸다.

그 후 DFS를 수행한 뒤에 도착점을 방문했다면 길이 있다고 판단할 수 있다.

 

💡 소스코드

---

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

public class P_1219 {
	static int[][] G;
	static boolean[] visited;
	static int flag;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sz;

		for (int TC = 1; TC <= 10; TC++) {
			sz = new StringTokenizer(br.readLine());

			TC = Integer.parseInt(sz.nextToken());//TestCase 번호
			int T = Integer.parseInt(sz.nextToken());//TestCase 수

			init();//Adjacency List, visited, flag 초기화

			String[] str = br.readLine().split(" ");

			for (int i = 0; i < T * 2; i += 2)
				G[Integer.parseInt(str[i])][Integer.parseInt(str[i + 1])] = 1;//연결된 Vertex는 1
			
			DFS(0);//DFS 실행
			
			if(visited[99])//도착지점이 True이면
				flag = 1;//flag = 1
			
			System.out.println("#" + TC + " " + flag);//출력

		}
		
		br.close();
	}

	public static void DFS(int V) {
		visited[V] = true;//방문한 노드는 True

		for(int i = 1; i < G.length; i++) {
			if(G[V][i] == 1 && !visited[i]) {//연결된 Vertex확인 후 방문하지 않았으면
				DFS(i);//DFS호출
			}
		}
	}

	public static void init() {
		G = new int[100][100];
		visited = new boolean[100];
		flag = 0;
	}
}

 

💡 결과

---