글 읽기 - BFS로 풀어보았는데 문제점을 못찾겠습니다 ㅠ

jarviskim88 6년 전 0

안녕하세요? 알고리즘 초보입니다!

https://www.acmicpc.net/problem/2178

미로 탐색 문제를 BFS로 풀어보았는데 한 13% 정도에서 틀렸다고 나오네요.

해당 코드를 설명드리자면, bfs 함수에서 깊이를 계산합니다. 깊이는 한번 Queue가 안에 들어있는 Queue를 비울때까지 입니다.

nextBfs 함수는 Queue안에 들어있는 좌표들을 다 비울때까지 입니다.(이게 다 비워지면 한 Depth를 탐색했다고 생각했습니다.)

여러 질문들도 검색해봤는데 저랑 비슷하게 푼거같은데 저는 어떤 부분에서 틀린지 잘 모르겠네요ㅠ

import java.util.*;

public class Main {

    private static int LOAD = 1;

    public static int bfs(int[][] map) {
        int n = map.length;
        int m = map[ 0 ].length;

        boolean[][] visited = new boolean[ n ][ m ];

        int count = 1;
        Queue<Position> queue = new LinkedList<>();
        queue.add(new Position(0, 0));
        visited[ 0 ][ 0 ] = true;

        while ( !queue.isEmpty() ) {
            queue = nextBfs(map, visited, queue, m, n);
            count++;
        }

        return count - 1;
    }

    static Queue<Position> nextBfs(int[][] map, boolean[][] visited, Queue<Position> queue, int m, int n) {
        Queue<Position> next = new LinkedList<>();

        while ( queue.size() > 0 ) {
            Position pos = queue.poll();
            int y = pos.y;
            int x = pos.x;

            if ( y > 0 && map[ y - 1 ][ x ] == LOAD && !visited[ y - 1 ][ x ]) {
                next.add(new Position(y - 1, x));
                visited[ y - 1 ][ x ] = true;
            }
            if ( y < n - 1 && map[ y + 1 ][ x ] == LOAD && !visited[ y + 1 ][ x ]) {
                next.add(new Position(y + 1, x));
                visited[ y + 1 ][ x ] = true;
            }
            if ( x > 0 && map[ y ][ x - 1 ] == LOAD && !visited[ y  ][ x - 1 ]) {
                next.add(new Position(y, x - 1));
                visited[ y ][ x - 1 ] = true;
            }
            if ( x < m - 1 && map[ y ][ x + 1 ] == LOAD && !visited[ y ][ x + 1]) {
                next.add(new Position(y, x + 1));
                visited[ y ][ x + 1 ] = true;
            }
        }

        return next;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] map = new int[ n ][ m ];

        scanner.nextLine();
        String line = null;
        for ( int i = 0; i < n; i++ ) {
            line = scanner.nextLine();
            String[] s = line.split("");
            for ( int j = 0; j < s.length; j++ ) {
                map[ i ][ j ] = Integer.parseInt(s[ j ]);
            }
        }
        System.out.println(bfs(map));
    }

    static class Position {
        public int y;
        public int x;

        public Position(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

BFS로 풀어보았는데 문제점을 못찾겠습니다 ㅠ

jarviskim88 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말