[Day20] 그래프 응용

가중치가 없는 그래프 - BFS (너비 우선 탐색) 사용

• 가중치가 없는 그래프에서 최단 경로를 찾을 때는 BFS가 가장 효율적이다.
• 예제 : 미로 찾기, 특정 정점까지의 최소 이동 횟수

BFS로 최단 경로 찾는 원리

1. 큐(Queue) 사용: 시작 정점을 큐에 넣고 탐색을 시작합니다.
2. 방문 체크 배열 사용: 중복 방문을 방지합니다.
3. 경로 저장
   • 배열을 이용하여 부모 노드를 저장
   • Node 클래스를 활용하여 각 정점의 부모를 기록
4. 목표 노드 도달 시 경로 추적

경로를 추적하기 위해 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

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);
        
        // 노드의 수 N과 간선의 수 M을 입력받음
        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);
        }
        
        // 시작 노드 S와 목표 노드 G를 입력받음
        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; // 시작 노드의 부모는 없음
        
        // BFS 탐색 시작
        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();
    }
}

---

경로를 추적하기 위해 parent의 정보를 가지는 정점 class를 사용하는 경우

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

import java.util.*;

public class BFS_Node_최단경로 {

    // 정점 class 정의
    static class Node {
        int vertex; // 정점 번호
        Node parent; // 부모 정점 (최단 경로 추적용)

        Node(int vertex, Node parent) {
            this.vertex = vertex;
            this.parent = parent;
        }
    }

    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];

        // BFS 탐색 시작
		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.vertex; // 현재 정점 번호

            // 현재 정점이 도착 정점과 같으면 경로를 찾았음
			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_미로탐색

백준_2178_미로탐색

/*
https://www.acmicpc.net/problem/2178
4 6
101111
101010
101011
111011
*/
import java.util.*;

public class 백준_2178_미로탐색 {
	static int N;
	static StringBuilder sb = new StringBuilder(100);
	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[][] arr=new int[N][M];
		
		boolean [][]isSelected=new boolean[N][M];
		
		sc.nextLine();
		for (int i = 0; i < N; i++) {
			String oneLine=sc.nextLine();
			
			for (int j = 0; j < M; j++) {
				arr[i][j]=oneLine.charAt(j)-'0';			
			}			
		}
		
		//BFS
		//1.Queue 만들기
		Queue<int[]> q=new LinkedList<>();

		//2.q에 start node를 넣는다
		int startX=0,startY=0;
		q.offer(new int[]{startX,startY});
		
		//3.방문체크
		isSelected[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(arr[curX][curY]);
			}
			
			for (int i = 0; i < 4; i++) {//4방 탐색
				int nx=curX+dx[i];
				int ny=curY+dy[i];
				
				if(nx>=0 && nx <N && ny>=0 && ny<M && arr[nx][ny]==1 && !isSelected[nx][ny]) {
					isSelected[nx][ny]=true;
					arr[nx][ny]=arr[curX][curY]+1;
					q.offer(new int[] {nx,ny});
				}
				
			}
		}		
		sc.close();
	}
}

---

TEAM STUDY

1. 백준 1697 - 숨바꼭질

• BFS로 최단 경로 찾기
• 순간이동, 전진, 후진의 3가지 조건 백준_1697_숨바꼭질

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

public class Main {

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

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

		boolean[] visited = new boolean[100001];
		Queue<int[]> q = new LinkedList<>();
		int time = 0;

		q.offer(new int[] { N, time });
		visited[N] = true;

		while (!q.isEmpty()) {
			int[] arr = q.poll();
			int cur = arr[0], curTime = arr[1];
			if (cur == K) {
				System.out.print(curTime);
				break;
			}

			if (cur * 2 <= 100000 && !visited[cur * 2]) {
				q.offer(new int[] { cur * 2, curTime + 1 });
				visited[cur * 2] = true;
			}
			if (cur + 1 <= 100000 && !visited[cur + 1]) {
				q.offer(new int[] { cur + 1, curTime + 1 });
				visited[cur + 1] = true;
			}
			if (cur - 1 >= 0 && !visited[cur - 1]) {
				q.offer(new int[] { cur - 1, curTime + 1 });
				visited[cur - 1] = true;
			}
		}
		sc.close();
	}
}

2. SWEA 2805 - 농작물 수확하기

import java.util.Scanner;

public class Solution {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		

		for (int i = 0; i < T; i++) {
			int N = sc.nextInt();
			int[][] farm = new int[N][N];
			int sum = 0;

			sc.nextLine();
			for (int j = 0; j < N; j++) {
				String str = sc.nextLine();
				for (int a = 0; a < N; a++) {
					farm[j][a] = str.charAt(a) - '0';
					sum += farm[j][a];
				}
			}

			// 전체 - 왼쪽 위 하얀 부분 삼각형 
			for (int x = 0; x < N / 2; x++) {
				for (int y = 0; y < N / 2 - x; y++) {
					sum -= farm[x][y];
				}
			}

			// 전체 - 오른쪽 위 하얀 부분 삼각형 
			for (int x = 0; x < N / 2; x++) {
				for (int y = N / 2 + x + 1; y < N; y++) {
					sum -= farm[x][y];
				}
			}

			// 전체 - 왼쪽 아래 하얀 부분 삼각형 
			for (int x = N / 2 + 1; x < N; x++) {
				for (int y = 0; y < x - N / 2; y++) {
					sum -= farm[x][y];
				}
			}

			// 전체 - 오른쪽 아래 하얀 부분 삼각형 
			for (int x = N / 2 + 1; x < N; x++) {
				for (int y = N - x + N / 2; y < N; y++) {
					sum -= farm[x][y];
				}
			}
			sb.append("#").append(i+1).append(" ").append(sum).append("\n");
		}
		System.out.println(sb);
		sc.close();
	}
}

---

END