[#20] 알고리즘 - 최단 경로

최단 경로

특정 두 노드 간의 거리를 최소화하는 것

 

가중치가 없는 그래프에서 정점간의 최단 경로를 찾는 방법은 BFS가 최고의 방법 !

단, 어떤 노드를 타고 내려왔는 지 경로를 추적해야 함 !

 

1️⃣ 경로를 추적하기 위해 parent 정보를 저장할 배열을 사용하는 경우

/*
	### 문제: 최단 경로 찾기
	
	**문제 설명**
	
	주어진 무방향 그래프에서 두 노드 간의 최단 경로를 찾는 프로그램을 작성하시오. 그래프는 N개의 노드와 M개의 간선으로 구성되어 있으며, 각 간선은 두 노드를 연결합니다. 시작 노드와 목표 노드가 주어질 때, 이 두 노드 간의 최단 경로를 출력하시오.
	
	**입력**
	
	- 첫째 줄에 두 개의 정수 N(1 ≤ N ≤ 1000)과 M(1 ≤ M ≤ 10000)이 주어진다. N은 노드의 개수, M은 간선의 개수이다.
	- 다음 M개의 줄에는 간선 정보가 주어진다. 각 줄은 두 개의 정수 u와 v(1 ≤ u, v ≤ N)를 포함하며, 이는 노드 u와 노드 v가 간선으로 연결되어 있음을 의미한다.
	- 마지막 줄에는 시작 노드 S와 목표 노드 G가 주어진다.
	
	**출력**
	
	- 시작 노드 S에서 목표 노드 G까지의 최단 경로를 출력한다. 경로는 노드 번호로 구성되어야 하며, 경로가 존재하지 않는 경우 `-1`을 출력한다.
	
	**입력**
	5 5
	1 2
	1 3
	2 4
	3 4
	4 5
	1 5
	
	**출력**
	1 2 4 5

*/

package graph;

import java.util.*;

public class BFS_최단경로 {

	static StringBuilder sb = new StringBuilder(); // 경로를 저장할 StringBuilder
	static boolean found = false; // 경로가 발견되었는지 여부를 저장하는 변수

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		List<List<Integer>> list = new ArrayList<>();

		for (int i = 0; i <= N; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < M; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();

			list.get(from).add(to);
			list.get(to).add(from);
		}

		int start = sc.nextInt();
		int goal = sc.nextInt();

		// 방문 여부 체크할 배열
		boolean[] visited = new boolean[N + 1];

		// 부모 노드를 저장할 배열(경로 추적 위함)
		int[] parent = new int[N + 1];

		// BFS를 위한 큐 초기화
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		visited[start] = true;
		parent[start] = -1; // 시작 노드의 부모는 없음

		while (!q.isEmpty()) {
			int cur = q.poll();

			// ** 하고 싶은 일 수행 **
			// 목표 노드에 도달한 경우
			if (cur == goal) {
				found = true;
				break; // 경로를 찾았으니 탐색 종료
			}

			// 현재 노드와 연결된 모든 노드를 탐색
			for (int i : list.get(cur)) {
				if (!visited[i]) {
					q.offer(i);
					visited[i] = true;
					parent[i] = cur; // 현재 노드를 부모로 설정
				}
			}

		}

		if (found) { // 경로가 발견된 경우
			// 목표 노드에서 시작 노드까지 부모를 통해 경로를 추적
			for (int at = goal; at != -1; at = parent[at]) {
				sb.append(at).append(" ");
			}
			System.out.println(sb.reverse().toString().trim());

		} else {
			System.out.println(-1);
		}

		sc.close();

	}

}

 

2️⃣ 경로를 추적하기 위해 정점 class를 사용하는 경우

/*
	무방향
	첫 째줄 정점개수 간선개수
	마지막줄 시작정점 도착정점
	가운데 간선정보(연결 정점)
	
	6 9
	1 2
	2 4
	2 5
	3 4
	3 6
	4 5
	4 6
	5 6
	1 4
	1 6
*/

package graph;

import java.util.*;

public class BFS_최단경로2 {

	// 노드의 정보를 저장할 class
	static class Node {
		int no; // 노드 번호
		Node parent; // 부모 노드(최단 경로 추적용)

		public Node(int no, Node parent) {
			super();
			this.no = no;
			this.parent = parent;
		}
	}

	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		List<List<Node>> list = new ArrayList<>();

		for (int i = 0; i <= N; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < M; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();

			list.get(from).add(new Node(to, null));
			list.get(to).add(new Node(from, null));
		}

		int start = sc.nextInt();
		int goal = sc.nextInt();

		// 방문 여부 체크할 배열
		boolean[] visited = new boolean[N + 1];

		Queue<Node> q = new LinkedList<>(); // Node 객체에 대한 주소가 저장될 큐
		q.offer(new Node(start, null));
		visited[start] = true;

		Node targetNode = null; // 최단 경로에서 도착 노드를 통해 부모 노드를 추적하기 위함

		while (!q.isEmpty()) {
			Node curNode = q.poll();
			int cur = curNode.no;

			// ** 하고 싶은 일 수행 **
			// 목표 노드에 도달한 경우
			if (cur == goal) {
				targetNode = curNode;
				break; // 경로를 찾았으니 탐색 종료
			}

			// 현재 노드와 연결된 모든 노드를 탐색
			for (Node n : list.get(cur)) {
				if (!visited[n.no]) {
					q.offer(new Node(n.no, curNode));
					visited[n.no] = true;
				}
			}

		}

		if (targetNode != null) {
			Node temp = targetNode;

			while (temp != null) {
				sb.insert(0, temp.no + " "); // 앞에 추가해 역순으로 경로 구성
				temp = temp.parent; // 부모 노드로 이동
			}
			System.out.println(sb);
		} else {
			System.out.println(-1);
		}

		sc.close();

	}

}

 

👩🏻‍💻 문제 풀어보기: 백준_미로 탐색_2178

package graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 백준_미로탐색_2178 {

	// 상, 우, 하, 좌 (시계 방향)
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		int[][] miro = new int[N][M];
		boolean[][] visited = new boolean[N][M];

		sc.nextLine();

		for (int i = 0; i < N; i++) {
			String line = sc.nextLine();
			for (int j = 0; j < M; j++) {
				miro[i][j] = line.charAt(j) - '0'; // 연산의 결과 int형
			}
		}

		// BFS
		// 1. Queue 만들기
		Queue<int[]> q = new LinkedList<>();

		// 2. q에 start node 넣기
		int startX = 0, startY = 0;
		q.offer(new int[] { startX, startY });

		// 3. 방문 체크
		visited[startX][startY] = true;

		// 4. q에서 데이터 꺼내 처리
		while (!q.isEmpty()) {
			int[] curV = q.poll();
			int curX = curV[0];
			int curY = curV[1];

			// 5. 하고 싶은 일 수행
			if (curX == N - 1 && curY == M - 1) {
				System.out.println(miro[curX][curY]);
				break;
			}

			// 사방 탐색
			for (int i = 0; i < 4; i++) {
				int nx = curX + dx[i];
				int ny = curY + dy[i];

				if (nx >= 0 && nx < N && ny >= 0 && ny < M && miro[nx][ny] == 1 && !visited[nx][ny]) {
					visited[nx][ny] = true;
					miro[nx][ny] = miro[curX][curY] + 1; // 1씩 더해주면서 결과적으로 마지막 칸 도착 시 지나온 최소 칸 수 저장
					q.offer(new int[] { nx, ny });
				}
			}
		}

		sc.close();

	}

}