글 읽기 - 14442 논리 질문

wooserk 3년 전 0

14442번 문제를 풀 때 visited[1001][1001][11] 처럼 벽을 부순 횟수에 따라 방문했는지를 체크해서 푼다는 것을 알았습니다.

혹시 벽을 부순 횟수가 아니라, 벽을 더 부술 수 있는지 없는지로 visited[1001][1001][2] 로 놓고 풀면 어떤 문제 또는 반례가 있는지 궁금합니다.

제가 아래 코드처럼 풀었었는데 틀렸습니다가 떠서 혹시 논리가 잘못된건지 궁금합니다.

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

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());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        // 맵 구성
        int[][] ary = new int[1001][1001];
        for(int i=1; i<=N; i++)
        {
            String str = br.readLine();

            for(int j=1; j<=M; j++)
                ary[i][j] = str.charAt(j-1) - '0';
        }

        int[] dr = {-1, 0, 0, 1};
        int[] dc = {0, -1, 1, 0};
        // K : 더 부술 수 있고/없고
        boolean[][][] check = new boolean[1001][1001][2];
        int[][] dist = new int[1001][1001];
        // 도달하지 못하면 -1.
        dist[N][M] = -1;
        // N과 M이 1일 경우를 대비해 나중에 선언
        dist[1][1] = 1;

        Queue<int[]> queue = new LinkedList<>();
        // [0] : row, [1] : col, [2] : cnt
        queue.add(new int[]{1, 1, 0});

        // 시작점은 다시 들를 수 없도록 설정
        check[1][1][0] = true;
        check[1][1][1] = true;

        while(!queue.isEmpty())
        {
            int[] tmp = queue.poll();

            for(int i=0; i<4; i++)
            {
                int newRow = tmp[0] + dr[i];
                if(newRow < 1 || newRow > N)
                    continue;
                int newCol = tmp[1] + dc[i];
                if(newCol < 1 || newCol > M)
                    continue;

                if(newRow == N && newCol == M)
                {
                    System.out.println(dist[tmp[0]][tmp[1]] + 1);
                    return;
                }

                // 더 이상 벽을 부술 수 없는 상태인지 저장
                int isGo = (tmp[2] == K) ? 1 : 0;

                // 벽이면
                if(ary[newRow][newCol] == 1)
                {
                    // 더 이상 부술 수 없는 상태면 갈 수 없음
                    if(isGo == 1)
                        continue;

                    // 이미 들른 길이면 최단 거리가 될 수 없음
                    if(check[newRow][newCol][isGo])
                        continue;

                    // 벽을 부수고 전진
                    check[newRow][newCol][isGo] = true;
                    dist[newRow][newCol] = dist[tmp[0]][tmp[1]] + 1;
                    queue.add(new int[]{newRow, newCol, tmp[2]+1});
                }

                // 길이면
                if(ary[newRow][newCol] == 0)
                {
                    // 이미 들른 길이면 최단 거리가 될 수 없음
                    if(check[newRow][newCol][isGo])
                        continue;

                    // 전진
                    check[newRow][newCol][isGo] = true;
                    dist[newRow][newCol] = dist[tmp[0]][tmp[1]] + 1;
                    queue.add(new int[]{newRow, newCol, tmp[2]});
                }
            }
        }

        System.out.println(dist[N][M]);
    }
}

playsworld16 3년 전 1

한 지점을 방문한 후에, 더 적게 부수고 그 지점을 도달하는 경우를 배제시킵니다.

반례 하나 드릴게요.

input:

4 4 2
0100
0001
0011
0110

output: -1

answer: 7

wooserk 3년 전 0

정말 감사합니다~!~!!

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

문제

문제

출처

ICPC

14442 논리 질문

wooserk 3년 전 0

playsworld16 3년 전 1

wooserk 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말