14496번: 그대, 그머가 되어
첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문
www.acmicpc.net
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);
}
}
'알고리즘 문제 풀이 > BOJ 실버' 카테고리의 다른 글
| [백준] 15900 - 나무 탈출 (0) | 2021.12.25 |
|---|---|
| [백준] 18428 - 감시 피하기 (1) | 2021.12.25 |
| [백준] 9934 - 완전 이진 트리 (0) | 2021.12.22 |
| [백준] 2346 - 풍선 터뜨리기 (0) | 2021.10.25 |
| [백준] 17276 - 배열 돌리기 (0) | 2021.10.10 |
| [백준] 1325 - 효율적인 해킹 (0) | 2021.09.25 |
| [백준] 5567 - 결혼식 (0) | 2021.08.08 |
