글 읽기 - [파이썬] HELP ME....오답 이유가 뭘까요?

tkddnjs1234 3년 전 0

로직은 https://rebas.kr/770 해당 블로그를 참고하여 구현하였습니다.

그런데 분명 똑같이 짠 것 같은데 채점 시 틀렸다고 나오네요...

틀렸다고 나오는 이유가 뭔가요?

# BOJ 9376

from collections import deque

def bfs(x,y):
    dist = [[-1]*(w+2) for _ in range(h+2)]   # 방문체크하고 갱신하기 위한 용도
    q = deque()
    q.append((x,y))
    dist[x][y]=0
    while q:
        x, y = q.popleft()
        for dx, dy in (-1,0),(1,0),(0,-1),(0,1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx > h+1 or ny < 0 or ny > w+1:
                continue
            if dist[nx][ny]>=0 or maze[nx][ny]=='*':
                continue
            if maze[nx][ny]=='#':
                dist[nx][ny]=dist[x][y]+1
                q.append((nx,ny))
            elif maze[nx][ny]=='.':
                dist[nx][ny]=dist[x][y]
                q.append((nx,ny))

    return dist


for _ in range(int(input())):
    h, w = map(int, input().split())
    maze=[]
    maze.append(list('.'*(w+2)))
    for _ in range(h):
        maze.append(list('.'+input().strip()+'.'))
    maze.append(list('.'*(w+2)))
    dq = deque()
    for i in range(h+2):
        for j in range(w+2):
            if maze[i][j]=='$':
                maze[i][j]='.'
                dq.append((i,j))
    sx, sy = dq.popleft()
    d1 = bfs(sx, sy)
    sx, sy = dq.popleft()
    d2 = bfs(sx, sy)
    d3 = bfs(0, 0)
    ans = 1000000000
    for i in range(h+2):
        for j in range(w+2):
            if maze[i][j]=='*':
                continue
            k = d1[i][j] + d2[i][j] + d3[i][j]
            if maze[i][j]=='#':
                k-=2
            ans = min(k,ans)

    print(ans)

palilo 3년 전 1

18 ~ 23번 줄에서

벽이 아닐 경우 deque의 앞에 넣어야 하고

벽일 경우 dist를 1 늘린 뒤 deque의 뒤에 넣어야 합니다.

tkddnjs1234 3년 전 0

코딩의 신님...정말 감사드립니다...

송구하오나 이유를 알 수 있을까요?

caritas1996 3년 전 1

'.' 과 '#' 이 둘 다 front 혹은 back으로 들어가면 먼저 dist가 갱신된 경우 올바른 값을 출력하지 못할 수 있어요.

front부터 빼내고 있기 때문에 '.'이 front로 들어가야 최솟값을 찾을 수 있어요.

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

문제

문제

출처

ICPC

[파이썬] HELP ME....오답 이유가 뭘까요?

tkddnjs1234 3년 전 0

palilo 3년 전 1

tkddnjs1234 3년 전 0

caritas1996 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말