BOJ_2644_촌수계산

1.

구분: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
언어: Java
전략

• 각 촌수의 연결 관계를 그래프로 보고, 이를 배열에 저장 - 연결되어있으면 true, 아니면 false(default)
• BFS로 그래프를 탐색 
• 촌수가 1씩 증가하는 것은, 나에게서 인접한 것들이다.
• 따라서 나와 인접한 것을 큐에 삽입할 때, 내 번호와 촌수를 함께 넣는다.

---

2. 코드

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

public class Main {
	
	static class Node{
		//q에 넣을 사람번호와 start기준 촌수 
		int item;
		int level;
		Node(int item, int level){
			this.item = item;
			this.level = level;
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt(); //전체 사람의 수
		int start = scanner.nextInt(); //찾으려는 사람1
		int target = scanner.nextInt(); //찾으려는 사람2
		int m = scanner.nextInt(); //관계의 수
		boolean[][] matrix = new boolean[n+1][n+1];
		int clevel=0; //처음 시작 촌수
		//친척 관계를 배열에 등록한다.
		for(int i = 0; i<m; i++) {
			int p = scanner.nextInt();
			int c = scanner.nextInt();
			matrix[p][c] = true;
			matrix[c][p] = true;
		}
		//친척인지 아닌지를 파악하는 boolean
		boolean okay = false;
		
		Queue<Node> q = new LinkedList<>();
		boolean[] check = new boolean[n+1]; //방문여부 확인 배열
		
		//시작점과 촌수를 넣고 방문처리
		q.offer(new Node(start, clevel));
		check[start] = true;
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			int current = node.item;
			clevel = node.level;
			//찾는 것과 같다면 그만 
			if(current == target)
			{
				//친척이라 확인
				okay = true;
				break;
			}	
			for(int i = 0; i<n+1; i++) {
				//방문 안하고, 둘이 인접해 있으면
				if(!check[i] && matrix[current][i])
					{
						//나의 아이템과, 촌수(나를 부른 것보다 1크게)를 q에 넣는다.
						q.offer(new Node(i,clevel+1));
						check[i] = true;
					}
			}
		}
		//친척이라면
		if(okay)
			System.out.println(clevel);
		else //친척이 아니라면
			System.out.println(-1);
		
		
		//bfs(start, target);
	}
}

---

3

BFS를 이용하면 풀 수 있다. 

백준의 토마토(7576)과 유사하다