[BOJ/Java] 2644 : 촌수계산

문제

 

www.acmicpc.net/problem/2644

2644번: 촌수계산

 

 

풀이

 

• 부모/자식간의 관계를 나타내는 relation이라는 이차원배열을 만들어 부모/자식간이면 1을, 아니라면 0이 들어있도록 한다 
• visit 체크도 필수

 

코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, m, personA, personB;
	static int[][] relation;
	static boolean[] visited;
	static int answer= -1;
	
	public static void main(String[] args) throws Exception{
		n = Integer.parseInt(in.readLine());
		st = new StringTokenizer(in.readLine());
		personA = Integer.parseInt(st.nextToken());
		personB = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(in.readLine());
		
		relation = new int[n+1][n+1];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(in.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			relation[A][B] = relation[B][A] = 1;
		}
		
		BFS(personA, personB);
		System.out.println(answer);
	}
	
	private static void BFS(int personA, int personB) {
		
		Queue<Person> que = new LinkedList<>(); 
		que.offer(new Person(personA, 0));
		visited = new boolean[n+1];
		while(!que.isEmpty()) {
			Person curPerson = que.poll();
			for(int i = 1; i <=n;i++) {				
				if(relation[curPerson.num][i] == 1 && !visited[i] ) {
					if(i == personB) {
						answer = curPerson.dist + 1;
						break;
					}
					visited[i] = true;
					que.offer(new Person(i, curPerson.dist + 1));
				}
			}
		}
	}
	
	private static class Person{
		int num;
		int dist;
		Person(int num, int dist){
			this.num = num;
			this.dist = dist;
		}
	}
}

 

 

느낀점

 

• 쉬운 문제인데도 유형이 익숙하지 않아서 조금 헤맸다