ํฐ์คํ ๋ฆฌ ๋ทฐ
[๋ฌธ์ ]
https://www.acmicpc.net/problem/5214
[ํ์ด]
BFS(๋๋น ์ฐ์ ํ์)์ ์ด์ฉํ์ฌ ํ์ดํ์์ต๋๋ค.
์ ๋ ฅ์ผ๋ก ๋ค์ด์ค๋ ์ซ์๋ค์ 2๊ฐ๋ก ๋๋์ด ์๊ฐํ์์ต๋๋ค.
tubeOut ๊ฐ ํ์ดํํ๋ธ๊ฐ ์ด๋ํ ์ ์๋ ์ญ ๋ฒํธ
tubeIn ๊ฐ ์ญ๋ค์ด ์ด๋ํ ์ ์๋ ํ์ดํํ๋ธ ๋ฒํธ
๋ฐ๋ผ์ ์์ 1๋ฒ์ ์ฌ์ฉํ๋ฉด tubeOut๊ณผ tubeIn๋ ์๋์ ๊ฐ์ด ๊ตฌ์ฑ๋ฉ๋๋ค.
๋ ArrayList๋ฅผ ํ์ฉํด์ findStation()๋ฅผ ํตํด BFS๋ฅผ ์งํํ๋ฉด,
( ์ด๋ N = 1์ด๋ผ๋ฉด ๋ฌด์ ๊ฑด 1๋ฒ๋ง์ ์ญ์ ์ด๋ ๊ฐ๋ฅํ๋ค๋ ์์ธ ์ฒ๋ฆฌ๋ฅผ ํ์ง ๋ชปํด 100%์์ ์ค๋ต์ฒ๋ฆฌ๊ฐ ๋๋ ๋ฌธ์ ๊ฐ ๋ฐ์ํ์์ต๋๋ค. )
1๋ฒ ์ญ -> 2,3ํ๋ธ๋ก ์ด๋ ๊ฐ๋ฅ ( 1๋ฒ ์ด๋ )
2๋ฒ ์ญ -> 1๋ฒํ๋ธ๋ ์ด๋ฏธ ๋ฐฉ๋ฌธํ์ผ๋ continue
3๋ฒ์ญ -> 3๋ฒ ํ๋ธ๋ก ์ด๋ ๊ฐ๋ฅ ( 2๋ฒ ์ด๋ )
3๋ฒ ํ๋ธ -> 3, 6, 7๋ฒ ์ญ์ผ๋ก ์ด๋ ๊ฐ๋ฅ
3๋ฒ ์ญ -> ์ด๋ฏธ ๋ฐฉ๋ฌธ ํ์ผ๋ continue
6๋ฒ ์ญ -> 4, 5 ํ๋ธ๋ก ์ด๋ ๊ฐ๋ฅ ( 3๋ฒ ์ด๋ )
5๋ฒ ํ๋ธ์ N์๊ฐ 9๊ฐ ์์ผ๋ฏ๋ก ( 4๋ฒ ์ด๋ ) 4๋ฅผ ์ถ๋ ฅํฉ๋๋ค.
[์ฝ๋]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Station implements Comparable<Station>{
int index;
int sum;
public Station(int index, int sum) {
this.index = index;
this.sum = sum;
}
@Override
public int compareTo(Station o) {
return this.sum - o.sum;
}
}
public class Main {
public static int N; // ์ญ์ ๊ฐ์
public static int K; // ํ ํ์ดํผํ๋ธ๊ฐ ์ฐ๊ฒฐํ๋ ์ญ์ ๊ฐ์
public static int M; // ํ์ดํผํ๋ธ์ ๊ฐ์
public static ArrayList<ArrayList<Integer>> tubeOut = new ArrayList<>(); // ๊ฐ ํ๋ธ๊ฐ ๊ฐ ์ ์๋ ์ญ ์ ์ฅ
public static ArrayList<ArrayList<Integer>> tubeIn = new ArrayList<>(); // ๊ฐ ์ญ์ด ๊ฐ ์์๋ ํ๋ธ ์ ์ฅ
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for(int i=0;i<=N;i++) {
tubeIn.add(new ArrayList<Integer>());
}
tubeOut.add(new ArrayList<Integer>());
for(int i=1;i<=M;i++) {
tubeOut.add(new ArrayList<Integer>());
st = new StringTokenizer(br.readLine());
for(int j=0;j<K;j++) {
int num = Integer.parseInt(st.nextToken());
tubeOut.get(i).add(num);
tubeIn.get(num).add(i);
}
}
findStation();
}
public static void findStation() {
if(N == 1) {
System.out.println(1);
return;
}
PriorityQueue<Station> pq = new PriorityQueue<>();
pq.offer(new Station(1, 1));
boolean[] visitTube = new boolean[M + 1];
boolean[] visitStation = new boolean[N + 1];
while(!pq.isEmpty()) {
Station p = pq.poll();
visitStation[p.index] = true;
for(Integer tube:tubeIn.get(p.index)) {
if(visitTube[tube]) {
continue;
}
visitTube[tube] = true;
for(Integer station:tubeOut.get(tube)) {
if(!visitStation[station]) {
visitStation[station] = true;
if(station == N) {
System.out.println(p.sum + 1);
return;
}
pq.offer(new Station(station, p.sum + 1));
}
}
}
}
System.out.println(-1);
}
}
'Algorithm > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[JavaScript] ๋ฐฑ์ค 2457๋ฒ - ๊ณต์ฃผ๋์ ์ ์ (0) | 2022.08.04 |
---|---|
[JavaScript] ๋ฐฑ์ค 1806๋ฒ - ๋ถ๋ถํฉ (0) | 2022.08.01 |
[Java] ๋ฐฑ์ค 2011๋ฒ - ์ํธ์ฝ๋ (0) | 2022.07.17 |
[Java] ๋ฐฑ์ค 16500๋ฒ - ๋ฌธ์์ด ํ๋ณ (0) | 2022.07.15 |
[Java] ๋ฐฑ์ค 5430๋ฒ - AC (0) | 2022.07.14 |
- Total
- Today
- Yesterday
- ๋ ์์ปฌ ํ๊ฒฝ
- ํจ์ํ ํ๋ก๊ทธ๋๋ฐ
- ํฌํฌ์ธํฐ
- map
- ํ๋กํ ์ฝ
- ์๋ฐ
- 2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด
- ๊ฐ์ฒด์งํฅ ํ๋ก๊ทธ๋๋ฐ
- JavaScript
- ํ๋กํผํฐ
- git
- ์ด๋ถํ์
- ์นด์นด์ค ์ธํด
- ๋ฐฑ์ค node.js
- ์ฝ๋ฉํ ์คํธ
- ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
- ๋ฐฑ์ค javascript
- fp
- ๋ชจ๋ ์๋ฐ์คํฌ๋ฆฝํธ deep dive
- ๋์์ธ ํจํด
- ๋ฐฑ์ค
- ์๋ฐ์คํฌ๋ฆฝํธ
- Baekjoon
- ๋คํธ์ํฌ
- ์๊ณ ๋ฆฌ์ฆ
- ์ด์์ฒด์
- ์ ์ญ ๋ณ์
- TDD
- http
- ํ๋ก๊ทธ๋๋จธ์ค
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |