글 읽기 - 자바 bfs로 풀었는데 시간초과가 떠요

yhs1020 6년 전 0

뭐가 문제일까요.. queue 사용해서 bfs로 풀었는데 시간초과가 뜹니다.

어느 부분을 줄여야 할까요 어떤부분이 시간을 많이 잡아먹는지..

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
        static int map[][];
        static int visit[][];
        static int m, n, k;
        static int[] dx={0,0,1,-1};
        static int[] dy={1,-1,0,0};

        static class Pos {
            int x;
            int y;
            int cnt;

            public Pos(int x, int y, int cnt) {//x,y,움직인 거리 카운트
                this.x = x;
                this.y = y;
                this.cnt = cnt;
            }
        }
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        visit = new int[n][m];

        for (int i = 0; i < n; i++) {
            String temp = sc.next();
            for (int j = 0; j < m; j++) {
                map[i][j] = (int)temp.charAt(j)-48;
            }
        }

        Pos pos = new Pos(0, 0, 1);
        Queue<Pos> q = new LinkedList<>();
        q.offer(pos);
        while (true) {
            pos = q.poll();

            visit[pos.x][pos.y] = 1;//방문
            for (int i = 0; i < 4; i++) {//4방면 검사
                if (pos.x + dx[i] >= 0 && pos.x + dx[i] < n && pos.y + dy[i] >= 0 && pos.y + dy[i] < m) {
                    if (map[pos.x + dx[i]][pos.y + dy[i]] == 1 && visit[pos.x + dx[i]][pos.y + dy[i]] == 0) {
                        //길이 있고 방문하지 않았으면
                        if (pos.x + dx[i] == n-1 && pos.y + dy[i] == m-1) {//마지막길일 경우 return
                            System.out.println(pos.cnt+1);
                            return;
                        }
                        q.offer(new Pos(pos.x + dx[i], pos.y + dy[i], pos.cnt + 1));
                    }
                }
            }
        }
    }
}

djm03178 6년 전 3

BFS할 때 많이 하는 실수인데요, 방문 체크를 큐에서 꺼낸 후에 할 게 아니라, 큐에 추가하는 과정에 해야 됩니다. 안 그러면 중복 방문을 하게 돼요.

예를 들어

과 같이 되어 있다면, 왼쪽 위에서 시작해서 다음 차례에 오른쪽 위, 왼쪽 아래를 가게 되겠죠. 그런데 각각의 점을 방문할 때 오른쪽 아래에 방문 체크가 안 되어있기 때문에 두 점에서 모두 오른쪽 아래 점을 큐에 넣게 됩니다. 결과적으로 오른쪽 아래 점은 2번 방문하게 됩니다.

yhs1020 6년 전 0

djm03178님 감사합니다

그걸 생각못했네요!

allen246 3년 전 0

@djm03178

감사합니다! 가끔씩 BFS할때 어떤건 빠르게 되고 어떤건 느린가 했더니 저걸 무의식적으로 쓰거나 안쓰거나 했었네요!

좋은 팁 알아갑니다 감사합니다!

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

문제

문제

출처

ICPC

자바 bfs로 풀었는데 시간초과가 떠요

yhs1020 6년 전 0

djm03178 6년 전 3

yhs1020 6년 전 0

allen246 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말