[백준] 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> 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 qu = new LinkedList(); 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); } }

결과 화면

from http://nato-blog.tistory.com/150 by ccl(S) rewrite - 2021-11-15 02:26:37