반응형
2644번 촌수 계산
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어
www.acmicpc.net
Comment
DFS, BFS를 첫 입문할 때 하기 좋은 그래프 문제이다. 해당 문제는 DFS적으로 접근하면 Depth를 잘 활용할 수 있었는데, BFS를 활용해서 풀어볼 때 문제가 생겼었다. 직면했던 문제는 BFS에서는 Depth를 어떤 기준으로 체크할 수 있을까? 라는 고민을 많이 하게 한 문제였다.
hint
DFS, BFS 두가지 방법 모두 풀린다.
하지만 체감 난이도는 BFS가 더 어려웠던 것 같다.
Solution
- DFS
재귀호출할 때 매개변수를 통해서 해당 깊이를 더해가며 풀어보니 잘 해결되었다.
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | import java.io.*; import java.util.*; public class Main { static boolean[] check; static ArrayList<Integer>[] al; static int n, m, start, target; static boolean flag; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()); start = Integer.parseInt(st.nextToken()); target = Integer.parseInt(st.nextToken()); m = Integer.parseInt(br.readLine()); al = new ArrayList[n + 1]; check = new boolean[n + 1]; for (int i = 0; i < n + 1; i++) { al[i] = new ArrayList<>(); } int x, y; for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); x = Integer.parseInt(st.nextToken()); y = Integer.parseInt(st.nextToken()); al[x].add(y); al[y].add(x); } check[start] = true; dfs(start, 0); if (!flag) { System.out.println(-1); } } static void dfs(int n, int count) { //7 3 if (n == target) { //도착하면 flag 변경 후 종료 flag = true; System.out.println(count); return; } else if (flag) { //이미 찾았으면 더이상 dfs를 돌 필요 없음 return; } else { for (int a : al[n]) { if (!check[a]) { check[a] = true; dfs(a, count + 1); } } } } } | cs |
- BFS
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | import java.io.*; import java.util.*; public class Main { static boolean[] check; static ArrayList<Integer>[] al; static int n, m, start, target; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()); start = Integer.parseInt(st.nextToken()); target = Integer.parseInt(st.nextToken()); m = Integer.parseInt(br.readLine()); al = new ArrayList[n + 1]; check = new boolean[n + 1]; for (int i = 0; i < n + 1; i++) { al[i] = new ArrayList<>(); } int x, y; for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); x = Integer.parseInt(st.nextToken()); y = Integer.parseInt(st.nextToken()); al[x].add(y); al[y].add(x); } bfs(start, target); } static void bfs(int start, int target) { // null을 활용해서 깊이 구분자를 생성 int count = 0; Queue<Integer> q = new LinkedList<>(); q.add(start); q.add(null); check[start] = true; while (!q.isEmpty()) { Integer now = q.poll();//null을 활용하기 위해 Integer로 if(now == null) {//null을 만날 때마다 깊이가 깊어짐 count++ if(!q.isEmpty()) { q.add(null); count++; } }else { for (int y : al[now]) { if (!check[y]) { check[y] = true; if (y == target) { // bfs깊이에 따라서 체크 후 해당 깊이 출력 System.out.println(count + 1); return; } q.add(y); } } } } System.out.println(-1); } } | cs |
내가 만질 때는 null을 Queue에 넣어서 구분자로 생각하고 null을 만날 때마다 count가 1씩 증가하도록 구현했었는데, 좀 더 직관적인 방법이 좋았을거라 생각했고, 스터디를 진행하는 다른 사람이 푼 것을 봤을 때 distance라는 배열을 만들어서 해당 값을 누적되게 구현했는데 더 좋은 방법 같았다.
어쨌든 그래프에서 DFS, BFS를 둘 다 사용해보기에 좋은 문제였던 것 같다!
반응형
'공부 > Algorithm' 카테고리의 다른 글
| 백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글 (0) | 2023.08.17 |
|---|---|
| 백준 골드5 달성! (0) | 2023.08.11 |
| 백준 2023번 신기한 소수 자바로 풀어 본 짧은 글 (0) | 2023.07.25 |
| 백준 2583번 영역 구하기 자바로 풀어 본 짧은 글 (0) | 2023.07.23 |
| 알고리즘 근황 (0) | 2023.07.23 |