글 읽기 - [파이썬] 60%에서 틀리시는 분들을 위한 글 (스포주의 정답 코드가 있습니다.)

iambyunghyun 2년 전 1

해답은 43번째 줄에 있습니다.

from collections import deque
def bfs(x,y):
    global graph
    visited = [[-1]*(w+2) for _ in range(h+2)]
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    q = deque()
    q.append([x,y])
    visited[x][y] = 0
    while q:
        a,b = q.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
            if nx>=0 and ny>=0 and nx<h+2 and ny<w+2 and visited[nx][ny] == -1:
                if graph[nx][ny]=="." or graph[nx][ny] == "$":
                    visited[nx][ny] = visited[a][b]
                    q.appendleft([nx,ny])
                elif graph[nx][ny] == "#":
                    visited[nx][ny] = visited[a][b] + 1
                    q.append([nx,ny])
    return visited

N = int(input())
for _ in range(N):
    h,w = map(int,input().split())
    graph = []
    graph.append(list("."*(w+2)))
    for i in range(h):
        graph.append(list(map(str,"."+input()+".")))
    graph.append(list("."*(w+2)))
    robber = []
    for i in range(h+2):
        for j in range(w+2):
            if graph[i][j] =="$":
                robber.append([i,j])
    v1 = bfs(robber[0][0],robber[0][1])
    v2 = bfs(robber[1][0],robber[1][1])
    v3 = bfs(0,0)
    result = int(1e9)
    for i in range(h+2):
        for j in range(w+2):
            if v1[i][j] != -1 and v2[i][j]!= -1 and v3[i][j]!=-1: # 이 조건이 없으면 60% 에서 틀렸다고 나옴
                temp = v1[i][j] + v2[i][j] + v3[i][j]

                if graph[i][j] == "*":
                    continue
                if graph[i][j] =="#":
                    temp -= 2
                result = min(result,temp)
    print(result)

k550706 1년 전 0

덕분에 답은 맞았습니다만, 저 코드가 무슨 유의미한 내용을 담고 있는건지 이해가 잘 안갑니다 ㅠ

ckwjdgur12 8달 전 0

죄수들의 위치와 상관없이 벽으로 둘러싸인 공간이 나온다면 중간 공간의 값은 -3이 나오게 됩니다. 그래서 틀린것같네요.

***
*.*
***

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

문제

문제

출처

ICPC

[파이썬] 60%에서 틀리시는 분들을 위한 글 (스포주의 정답 코드가 있습니다.)

iambyunghyun 2년 전 1

k550706 1년 전 0

ckwjdgur12 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말