글 읽기 - 같은 수의 거울을 사용했을 때, 이미 방문한 정점을 왜 방문해야하나요?

nmrhtn7898 2년 전 0

이미 정점을 방문했더라도 더 적은 수의 거울을 사용했을 때는 방문을 허용해야 하는 것을 이해했습니다.

하지만 같은 수의 거울을 사용했을 때, 방문을 왜 허용해주어야 하는지 잘 모르겠습니다.

84번 라인에서 check[nx][ny] < nc가 check[nx][ny] <= nc으로 바뀌어도 된다고 생각하는데

어떤 경우에서 같은 수의 거울을 사용했을 때도 재방문이 필요한걸까요...?

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static int n;

    public static int m;

    public static char[][] map;

    public static int[][] check;

    public static int[] dx = {-1, 0, 1, 0};

    public static int[] dy = {0, 1, 0, -1};

    public static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))) {
            StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
            m = Integer.parseInt(stringTokenizer.nextToken());
            n = Integer.parseInt(stringTokenizer.nextToken());
            map = new char[n][m];
            check = new int[n][m];

            int sx = -1;
            int sy = -1;
            int ex = -1;
            int ey = -1;

            for (int i = 0; i < n; i++) {
                String s = reader.readLine();
                for (int j = 0; j < s.length(); j++) {
                    map[i][j] = s.charAt(j);
                    if (map[i][j] == 'C') {
                        if (sx == -1) {
                            sx = i;
                            sy = j;
                        } else {
                            ex = i;
                            ey = j;
                        }
                    }
                }
            }

            bfs(sx, sy, ex, ey);
            writer.write(answer + "");
        }
    }

    public static void bfs(int sx, int sy, int ex, int ey) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sx, sy, -1, 0});
        check[sx][sy] = 1;

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            int d = poll[2];
            int c = poll[3];

            if (x == ex && y == ey) {
                answer = Math.min(answer, c);
                continue;
            }

            for (int i = 0; i < dx.length; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (check(nx, ny)) {
                    continue;
                }

                int nc = d != -1 && d != i ? c + 1 : c;

                if (check[nx][ny] != 0 && check[nx][ny] < nc) { // check[nx][ny] <= nc
                    continue;
                }

                check[nx][ny] = nc;
                queue.add(new int[]{nx, ny, i, nc});
            }
        }
    }

    public static boolean check(int x, int y) {
        return x < 0 || y < 0 || x >= n || y >= m || map[x][y] == '*';
    }

}

knight7024 2년 전 1

동일한 개수의 거울을 사용했어도 이전 정점에서 현재 정점으로 올 때의 방향이 다르면 다른 결과가 나올 수도 있기 때문인 거 같습니다.

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

문제

문제

출처

ICPC

같은 수의 거울을 사용했을 때, 이미 방문한 정점을 왜 방문해야하나요?

nmrhtn7898 2년 전 0

knight7024 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말