글 읽기 - 어디가 틀렸는지 모르겠어요 (python)

ckatodmlrna 2년 전 0

python 사용하고 deque 사용했습니다.

반례 들었던 문제들도 시행해 봤는데 다 문제가 없어서요..

방법으로는

1. 죄수 1,2 모두 deque 사용 -> $ 만날때(다른 죄수를 만났을 때)와 외부로 나갈때 모두 각각 지나온 문 저장

2. 죄수1이 외부로 나간 방법들과 죄수 2를 만날때 지나온 문들을 합친 후 set을 통해 중복 제거, 죄수2도 반복

3 . 죄수1이 외부로 나간 방법 + 죄수2가 외부로 나간 방법의 중복 제거

혹시 반례를 알 수 있을까요? ㅠ

import sys
from collections import deque

N = int(sys.stdin.readline())
H = []
W = []
maps = []
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for _ in range(N):
    h, w = map(int,sys.stdin.readline().split())
    H.append(h)
    W.append(w)
    map_ = []
    for _ in range(h):
        map_.append(list(sys.stdin.readline())[:-1])
    maps.append(map_)
    

def solution(h,w, map_,prisoner_q):
    global VISITED
    finds = []
    outs = []
    while prisoner_q:
        x, y, open_door = prisoner_q.pop()
        for sx, sy in zip(dx,dy):
            newx = x+sx
            newy = y+sy
            if validation(newx,newy,h,w):
                if not VISITED[newx][newy]:
                    if map_[newx][newy]=='.':
                        prisoner_q.appendleft((newx,newy,open_door))
                        VISITED[newx][newy]=True
                    elif map_[newx][newy]=='#':
                        prisoner_q.appendleft((newx,newy,open_door+[(newx,newy)]))
                        VISITED[newx][newy]=True
                    elif map_[newx][newy]=='$':
                        finds.append(open_door)
            elif not validation(newx,newy,h,w):
                outs.append(open_door)
                
                    

                        
    return finds, outs

def validation(x,y,h,w):
    if x>=0 and y>=0 and x<h and y<w:
        return True
    return False

def find_prisoner(H,W, map_, prisoner_q):
    global VISITED
    for h in range(H):
        for w in range(W):
            if map_[h][w]=='$':
                prisoner_q.appendleft((h,w,[]))
            


for h, w, map_ in zip(H,W,maps):
    prisoner_q1 = deque()
    prisoner_q2 = deque()
    
    find_prisoner(h,w,map_, prisoner_q1)
    
    prisoner_q2.append(prisoner_q1.pop())
    #죄수 1의 외부로 나가는 방법과 다른 죄수를 만나는 방법 서치
    VISITED = [[False]*w for _ in range(h)]
    VISITED[prisoner_q1[0][0]][prisoner_q1[0][1]]=True
    finds1, outs1 = solution(h,w,map_,prisoner_q1)
    #지나온 문들의 갯수를 저장
    result1 = [len(set(find+out))for find in finds1 for out in outs1]
    
    #죄수 2의 외부로 나가는 방법과 다른 죄수를 만나는 방법 서치
    VISITED = [[False]*w for _ in range(h)]
    VISITED[prisoner_q2[0][0]][prisoner_q2[0][1]]=True
    finds2, outs2 = solution(h,w,map_,prisoner_q2)
    #지나온 문들의 갯수를 저장
    result2 = [len(set(find+out))for find in finds2 for out in outs2]

    #외부로만 다니는게 가장 적을 수 있으므로 외부로 나가는 방법들만 저장
    result3 = [len(set(out1+out2)) for out1 in outs1 for out2 in outs2]
    
    #가장 작은 수 print
    print(min(result1+result2+result3))

kdh6429 2년 전 0

https://ideone.com/Z1olCr

코드를 돌려봤는데 에러가 나는것 같습니다.

눈으로 봤을땐, 각 조건이 최단경로로 만들어진 수인지 보장할 수 없을 것 같습니다..

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

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠어요 (python)

ckatodmlrna 2년 전 0

kdh6429 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말