-
[백준] 2644 촌수계산 - Java알고리즘 문제 풀이 2024. 6. 3. 20:15
문제 - 촌수계산
https://www.acmicpc.net/problem/2644
접근 방법
이 문제도 그래프 완전 탐색 문제이다 즉, bfs와 dfs로 문제를 풀 수 있다
작자는 dfs로 문제를 풀었다
코드 작성
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int n; static int m; static int start; static int end; static int[][] map; static int[] dist; public static void main(String[] args) throws IOException { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { n = Integer.parseInt(br.readLine()); map = new int[n + 1][n + 1]; dist = new int[n + 1]; StringTokenizer st = new StringTokenizer(br.readLine()); start = Integer.parseInt(st.nextToken()); end = Integer.parseInt(st.nextToken()); m = Integer.parseInt(br.readLine()); for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); map[x][y] = map[y][x] = 1; } dfs(start); System.out.println(dist[end] == 0 ? -1 : dist[end]); } } public static void dfs(int start) { if (start == end) { return; } for (int i = 1; i <= n; i++) { if (map[start][i] == 1 && dist[i] == 0) { dist[i] = dist[start] + 1; dfs(i); } } } }
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 11728 배열 합치기 - Java (0) 2024.06.24 [백준] 1644 소수의 연속합 - Java (0) 2024.06.16 [백준] 4963 섬의 개수 - Java (1) 2024.06.02 [백준] 1012 유기농 배추 - Java (0) 2024.05.30 [프로그래머스] 네트워크 - Java (0) 2024.05.30