개발자 톡
연습문제 톡
[HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길
촐퇴근길 문제 풀 경우 31-2 번 문제부터 런타임 에러가 발생합니다.
- 등록일
- 2023-05-05 22:01:52
- 조회수
- 534
- 작성자
- supren
import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()) + 1; int m = Integer.parseInt(st.nextToken()) + 1; boolean[][] map = new boolean[n][m]; boolean[][] reverseMap = new boolean[n][m]; for (int i = 1; i < m; i++){ st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); map[x][y] = true; reverseMap[y][x] = true; } st = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st.nextToken()); int end = Integer.parseInt(st.nextToken()); boolean[] fromStart = new boolean[n]; fromStart[end] = true; bfs(map, fromStart, start);// dfs(map, fromStart, start); boolean[] fromEnd = new boolean[n]; fromEnd[start] = true; bfs(map, fromEnd, end);// dfs(map, fromEnd, end); boolean[] reverseFromStart = new boolean[n]; bfs(reverseMap, reverseFromStart, start);// dfs(reverseMap, reverseFromStart, start); boolean[] reverseFromEnd = new boolean[n]; bfs(reverseMap, reverseFromEnd, end);// dfs(reverseMap, reverseFromEnd, end); int count = 0; for (int i = 1; i < n; i++) { if (fromStart[i] && fromEnd[i] && reverseFromEnd[i] && reverseFromStart[i]) { count ++; } } System.out.println(count - 2); } static public void bfs(boolean[][] map, boolean[] visited, int start) { Queue<Integer> q = new LinkedList<>(); q.add(start); visited[start] = true; while (!q.isEmpty()) { int cur = q.poll(); for (int i = 0; i < map[cur].length; i++) { if (map[cur][i] && !visited[i]) { q.add(i); visited[i] = true; } } } } public static void dfs(boolean[][] map, boolean[] visited, int start) { if (visited[start]) { return; } visited[start] = true; for (int i = 0; i < map[start].length; i++) { if (map[start][i] && !visited[i]) { dfs(map, visited, i); } } }}
알고리즘은 정확합니다. 다만 자바로 해결 할 수 없는 문제인가요??
#[hsat_6회_정기_코딩_인증평가_기출]_출퇴근길
#java