[백준] 14496 - 그대, 그머가 되어

[문제링크]

14496번: 그대, 그머가 되어

 

0. a-b 두 노드간 최단 거리 구하기

 

1. 다익스트라, 벨만 포드 등 다양하게 풀이 가능하다

 

2. bfs로 탐색, 목표 노드가 발견되는 즉시 탈출

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int a = pint(st.nextToken())-1;
		int b = pint(st.nextToken())-1;
		
		st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			adjList.add(new ArrayList<>());
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = pint(st.nextToken())-1;
			int to = pint(st.nextToken())-1;
			
			adjList.get(from).add(to);
			adjList.get(to).add(from);
		}
		
		int count=-1;
		boolean findAns=false;
		boolean[] isVisit = new boolean[n];
		Queue<Integer> qu = new LinkedList<Integer>();
		qu.offer(a);
		while(!qu.isEmpty()) {
			count++;
			int len = qu.size();
			for (int i = 0; i < len; i++) {
				int cur = qu.poll();
				if(cur==b) {
					findAns=true;
					break;
				}
				
				for(int next : adjList.get(cur)) {
					if(!isVisit[next]) {
						isVisit[next]=true;
						qu.offer(next);
					}
				}
			}
			if(findAns)break;
		}
		
		System.out.println(findAns?count:-1);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면