알고리즘 스터디 7주차 - 1

2644

• 알고리즘 : 그래프탐색
• 난이도 :실버3

문제

2644

접근

• 노드를 담는 리스트 배열을 만든다.
• 해당 노드를 dfs로 검사하면서 깊이를 추적한다.
• 깊이를 추적하지 못하면 -1
• 깊이를 리턴한다.

가정

• 깊이우선탐색을 하여도 시간초과가 나지 않을 것이다.

풀어보기

package org.example;

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

public class Main {
	static int n;
	static int start;
	static int end;
	static int m;
	private static ArrayList<Integer>[] nodes;
	private static boolean[] visited;
	private static int result = -1; // 결과를 저장할 변수 (-1로 초기화하여 경로가 없을 경우를 처리)

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(reader.readLine());
		String[] temp = reader.readLine().split(" ");
		start = Integer.parseInt(temp[0]);
		end = Integer.parseInt(temp[1]);
		m = Integer.parseInt(reader.readLine());
		nodes = new ArrayList[n + 1];
		visited = new boolean[n + 1]; // 방문 배열 초기화

		for (int i = 1; i <= n; i++) {
			nodes[i] = new ArrayList<>();
		}

		for (int i = 1; i <= m; i++) {
			String[] tempNode = reader.readLine().split(" ");
			int nodeStart = Integer.parseInt(tempNode[0]);
			int nodeEnd = Integer.parseInt(tempNode[1]);
			nodes[nodeStart].add(nodeEnd);
			nodes[nodeEnd].add(nodeStart);
		}

		dfs(start, 0);

		System.out.println(result);
	}

	static void dfs(int currentNode, int currentDepth) {
		if (currentNode == end) {
			result = currentDepth; // 목표 지점에 도달했을 때 깊이를 저장
			return;
		}

		visited[currentNode] = true;

		for (int adjacentNode : nodes[currentNode]) {
			if (!visited[adjacentNode]) {
				dfs(adjacentNode, currentDepth + 1);
			}
		}

		visited[currentNode] = false; // 백트래킹 시 방문 표시 해제
	}
}

시행착오

• visited 배열을 초기화 하지 않아서 시간초과가 발생 했다.
• 위와 같이 구현 시 백트래킹 시 방문 표시를 해제 하지 않으면 조기에 종료되어 모든 그래프를 탐색하지 못하는 버그가 발생한다.