개발자 톡

연습문제 톡 [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

이 카테고리의 톡 더보기