1219번 - 길찾기

문제의 저작권은 SW Expert Academy에 있습니다.

1. 문제
   1-1. 링크
   1-2. 문제 해석
2. 코드
3. 실행시간

 

 

---

 

 

1. 문제

1-1. 링크

SW Expert Academy

 

1-2. 문제 해석

A에서 B로 가는 길이 존재하는지를 묻는 문제이다.

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)으로 풀 수 있는데 나는 익숙한 DFS로 풀었다.

문제를 풀기 위해 알아두면 좋은 내용은 다음과 같다.

 

• 데이터 저장 가이드와 입력

우선 문제에서 주어진 [데이터 저장 가이드]와 [입력]을 유심히 볼 필요가 있다.

만약 한 정점에서 길이 N개로 갈릴 수 있다고 하면 NxN 배열을 선언해서 정점과 정점의 관계를 저장해야 할 텐데

이 문제에서는 최대 2개의 길로 나눠질 수 있다고 주어진다.

그래서 [데이터 저장 가이드]에서는 N개 짜리 배열을 2개 선언하라고 가이드를 주어주는 것이다. (친... 친절해 😍)

물론 Nx2 짜리 배열을 선언해도 된다.

 

 

문제 풀이에 사용된 Nx2 짜리 load 배열

 

나는 코드를 짤 때 위와 같은 배열에 데이터를 저장했다.

예를 들어 9번 정점이 어떤 정점과 연결되어 있는지를 알고 싶다면 idx가 9인 곳의 배열 값을 보면 된다.

위 표에서는 [idx][0]에 8, [idx][1]에 10이 저장되어 있으니 8번 정점, 10번 정점과 연결되어 있다는 것을 알 수 있다.

만약 load[idx][0]에만 데이터가 있다면 연결된 정점이 한 개뿐이라는 것이고

배열에 값이 없다면 (초기값인 0이 들어있을 것이다) 연결된 정점이 없다는 뜻이다.

 

또 다른 데이터 저장 방식으로는 LinkedList를 구현할 때처럼 사용자 정의 클래스를 만드는 방법이 있다.

하지만 입력 데이터가 정점이 이어지는 순서로 주어지지 않고 뒤죽박죽이기 때문에

데이터를 정리해서 다른 자료구조에 저장했다가 그걸 다시 객체에 저장해 야하기 때문에... 음...

이 방법은 이 문제에선 별로라고 생각이 들었다.

 

• 재귀 함수? 스택?

나는 예전부터 DFS 구현할 때 재귀 함수가 더 쉽게 느껴졌고 그렇게 구현해왔다.

하지만 이번 알고리즘 문제의 카테고리가 '스택'인 만큼 스택으로도 한 번쯤은 짜 봐야 하지 않나... 생각이 들었다.

둘의 실행 속도 차이가 있다는 글은 못 봤기 때문에 평소에는 자기가 구현하기 편한 걸로 하면 될 것 같고

그래도 둘 중 하나를 아예 구현할 줄 모르는 것보다는 할 줄 아는 것이 의미가 있을 것 같다.

 

 

2. 코드

• 재귀 함수를 이용한 DFS 코드

public class Day4_1219_길찾기 {
	static int[][] load;
	static int answer;
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		for (int tc = 1; tc <= 10; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			st.nextToken(); // 테스트케이스는 따로 입력받지 않았음
			int N = Integer.parseInt(st.nextToken());
			load = new int[N][2];

			st = new StringTokenizer(br.readLine(), " ");
			while (st.hasMoreTokens()) {
				int idx = Integer.parseInt(st.nextToken());
				int val = Integer.parseInt(st.nextToken());

				if (load[idx][0] == 0) load[idx][0] = val;
				else load[idx][1] = val;
			}

			answer = 0;
			dfs(0);
			
			sb.append("#").append(tc).append(" ").append(answer).append("\n");
		}
		System.out.println(sb.toString());
	}
	
	public static void dfs(int cur) {
		if(answer == 1 || cur == 0) return; // 도착지를 이미 찾았거나 길이 없다면
		
		if(cur == 99) { // 원하는 도착지에 도착하면
			answer = 1;
			return;
		}
		
		dfs(load[cur][0]); // 왼쪽 길 탐색
		dfs(load[cur][1]); // 오른쪽 길 탐색
	}
}

 

• 스택을 이용한 DFS 코드 (쓰레기 코드 주의)

public class Day4_1219_길찾기 {
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		for(int tc = 1; tc <= 10; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			st.nextToken(); // 테스트케이스는 따로 입력받지 않았음
			int N = Integer.parseInt(st.nextToken());
			int[][] load = new int[N][2];
			
			st = new StringTokenizer(br.readLine(), " ");
			while (st.hasMoreTokens()) {
				int idx = Integer.parseInt(st.nextToken());
				int val = Integer.parseInt(st.nextToken());

				if (load[idx][0] == 0) load[idx][0] = val;
				else load[idx][1] = val;
			}
			
			Stack<Integer> stack = new Stack<Integer>();
			stack.add(0); // 출발지점
			int result = 1;
			int preNode = 0;
			int nextNode;
			
			while(true) {
				if(stack.isEmpty()) {
					result = 0;
					break; // 길이 없다면 길찾기 종료
				}
				int curNode = stack.peek();
				
				// 첫 번째 길이 있는 경우 | 두 번째 길이 있는 경우 | 길이 없는 경우
				if(load[curNode][0] > 0) {
					nextNode = load[curNode][0];
				}
				else if(load[curNode][1] > 0) {
					nextNode = load[curNode][1];
				}
				else {
					if(load[preNode][0] == curNode) {
						load[preNode][0] = 0;
					}
					else {
						load[preNode][1] = 0;
					}
					stack.pop(); // pop하고
					continue; // 이전길로 돌아가
				}
				
				if(nextNode == 99) break; // 도착한 경우
				preNode = curNode; // 이전 노드 위치 저장
				stack.add(nextNode); // 다음 노드로 이동
			}
			
			sb.append("#").append(tc).append(" ").append(result).append("\n");
		}
		
		System.out.println(sb.toString());
	}
}

처음으로 스택을 이용해 DFS를 짜 봤는데 쓰레기 코드가 탄생했다.

혼자 힘으로 짜 봤다는 것에 의의를 두자...

 

 

3. 실행시간

재귀 + DFS 실행결과

 

재귀를 사용한 실행 결과는 무난 무난 괜찮게 나오는 것 같다.

 

 

반복문 + 스택 실행결과

 

충격과 공포의 스택을 이용한 결과... 반에서 꼴등을 했다.

물론 원래 스택이 이렇게 느린 게 아니라 내가 코드를 못 짠 탓이다.

 

 

 

 

 

 

---

💡 느낀 점

• 역시 DFS 구현은 재귀지! 구현하기도 편하고! 보기도 편하고!
• 정답자는 다른 사람 코드 볼 때 포인트를 안 깎았으면 좋겠다. 어차피 맞춘 건데! 다른 사람 코드 보고 오 이 사람은 이렇게도 짰네? 이런 부분을 내가 참고하면 좋겠구나! 이러면 얼마나 좋냐구요...

---