글 읽기 - 맞췄는데 이해가 되지 않는 부분이 있어서 질문 드립니다.

grapecw 3년 전 0

통과된 코드를 그대로 올려드립니다.

저는 방문 표시를 int[][]배열로 하였고, 그 방문된 장소를 벽을 부신 갯수로 저장하고, 만약 그곳가지 벽을 부시고 도착한 갯수가 적다면 그대로 진행하지만, 만약 벽을 더 많이 부시고 도착했으면 continue를 하게 만들었습니다.

그런데 처음에 낸 코드는 58~60번 줄의

// 밑에서 방문 표시를 해준 곳에 큐가 여러번 들어가므로 다시 한번 검사
else if (visited[curr.y][curr.x] < curr.broken)
continue;

를 없이 제출하니 실패가 떴습니다.

즉, 큐에 한번 방문 표시가 된 곳이 벽을 부시고 들어간게 크더라도 여러번 들어가서 시간 초과가 뜨는 것 같은데
디버깅을 해봐도 이유를 알 수 없더군요.

혹시 원인이 뭔지 알려주실 수 있으십니까?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int[][] way = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) throws IOException {
        int n, m, k;
        boolean[][] maze;

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
        }
        maze = new boolean[n][m];

        {
            String inputLine;
            for (int i = 0; i < n; i++) {
                inputLine = bf.readLine();
                for (int j = 0; j < m; j++) {
                    if (inputLine.charAt(j) == '1')
                        maze[i][j] = true;
                    else
                        maze[i][j] = false;
                }
            }
        }
        bf.close();

        int result = getShortedtRoute(n, m, k, maze);
        System.out.println(result);
    }

    // 가장 짧은 이동 경로를 반환하는 함수
    private static int getShortedtRoute(int n, int m, int k, boolean[][] maze) {
        Queue<Location> queue = new LinkedList<>();
        int[][] visited = new int[n][m];    // 방문을 int로 저장, 벽을 부신 횟수를 저장한다.
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        Location curr = new Location(0, 0, 0, 1);
        queue.add(curr);
        visited[0][0] = 0;
        int nextY, nextX;
        while (!queue.isEmpty()) {
            curr = queue.poll();
            if (curr.y == n - 1 && curr.x == m - 1)
                return curr.moveCnt;
            // 밑에서 방문 표시를 해준 곳에 큐가 여러번 들어가므로 다시 한번 검사
            else if (visited[curr.y][curr.x] < curr.broken)
                continue;
            for (int[] next : way) {
                nextY = next[0] + curr.y;
                nextX = next[1] + curr.x;
                if (nextY < 0 || nextX < 0 || nextY >= n || nextX >= m || visited[nextY][nextX] <= curr.broken)
                    continue;
                    // 만약 벽일 경우 부실 수 있나, 없나 검사하고 방문을 현재까지 벽을 부신 갯수를 저장한다.
                else if (maze[nextY][nextX]) {
                    if (curr.broken >= k)
                        continue;
                    queue.add(new Location(nextY, nextX, curr.broken + 1, curr.moveCnt + 1));
                    visited[nextY][nextX] = curr.broken + 1;
                } else {
                    queue.add(new Location(nextY, nextX, curr.broken, curr.moveCnt + 1));
                    visited[nextY][nextX] = curr.broken;
                }
            }
        }
        return -1;
    }
}

class Location {
    int y;  // 현재 위치의 y좌표
    int x;  // 현재 위치의 x좌표
    int broken;     // 부신 벽의 갯수
    int moveCnt;    // 현재 움직인 간의 갯수

    Location(int y, int x, int broken, int moveCnt) {
        this.x = x;
        this.y = y;
        this.broken = broken;
        this.moveCnt = moveCnt;
    }
}

grapecw 3년 전 0

자문 자답입니다.

68번째 줄에 문제가 있었네요. 현재 broken이 아니라 넣을 broken 기준으로 생각해야 됬습니다.

if (curr.broken >= k || visited[nextY][nextX] <= curr.broken + 1)
    continue;

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

문제

문제

출처

ICPC

맞췄는데 이해가 되지 않는 부분이 있어서 질문 드립니다.

grapecw 3년 전 0

grapecw 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말