글 읽기 - 문제를 풀긴 했지만 궁금한점..?

iron1209 5년 전 0

저는 이 문제를 풀때 dp[y][x][벽을 뚫고 지나갔는지 여부]이걸 통해서 풀었지만, 다시 한번 생각해보니 dp[y][x]로만 해도 충분하다고 생각합니다.

왜냐하면, 벽을 뚫었는지 여부는 그냥 큐를 통해서 기록해주면 된다고 생각했기 때문입니다. 이미 뚫고 지나갔는지 확인해서 이미 뚫었다면 벽을 안지나가면 되는거고, 안뚫었다면 뚫는 것까지 생각해서 진행해 주면 되니까요.

밑의 코드는 제 생각을 담은 틀린 코드입니다. 몇번 생각을 해보고 제출해봤는데 아무래도 경험적으로 dp[y][x]로만 푸는건 틀린것 같습니다. 그런데 왜 틀렸는지가 납득이 되질 않습니다. 혹시 저 처럼 생각해보신 분이 계신가요?

from collections import deque
input=__import__('sys').stdin.readline
n,m = map(int, input().split())
mp = [(input()) for _ in range(n)]
d = [[float("inf")]*m for _ in range(n)]
d[0][0] = 1
q=deque([(1,0,0,False)])
dx,dy=[0,0,1,-1],[1,-1,0,0]
while q:
    cost,y,x,hasBreak = q.popleft()
    if x==m-1 and y==n-1:
        continue
    for i in range(4):
        ny,nx = y+dy[i],x+dx[i]
        if 0<=ny<n and 0<=nx<m:
            if hasBreak==False and mp[ny][nx]=='1':
                if d[ny][nx]>cost+1:
                    d[ny][nx]=cost+1
                    q.append((cost+1,ny,nx,True))
            if d[ny][nx]>cost+1 and mp[ny][nx]=='0':
                d[ny][nx]=cost+1
                q.append((cost+1,ny,nx,hasBreak))
if d[n-1][m-1]!=float("inf"):
    print(d[n-1][m-1])
else:
    print(-1)

djm03178 5년 전 1

https://www.acmicpc.net/board/...

iron1209 5년 전 0

찾아 보다가 이 반례를 찾지 못했다는것을 발견하였습니다.

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

문제

문제

출처

ICPC

문제를 풀긴 했지만 궁금한점..?

iron1209 5년 전 0

djm03178 5년 전 1

iron1209 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말