글 읽기 - 5번 케이스 안맞음, 바로 틀림

ebbunnim 3년 전 0

bfs로 푸려고 했는데, 5번 케이스가 계속 틀립니다.. ㅠㅠ 이유가 뭘까요

from collections import deque

def iswall(x1,y1,x2,y2):
    if arr[x1][y1] == '#' and arr[x2][y2] == '#':
        return True
    elif arr[x1][y1] == '#':
        return (x1,y1) # 이 애들이 벽이다.
    elif arr[x2][y2] == '#':
        return (x2,y2)
    else:
        return False

def isout(x1,y1,x2,y2):
    if ((0>x1 or x1>=N) or (0>y1 or y1>=M)) and ((0>x2 or x2>=N) or (0>y2 or y2>=M)):
        return True
    elif ((0>x1 or x1>=N) or (0>y1 or y1>=M)):
        return (x1,y1)
    elif ((0>x2 or x2>=N) or (0>y2 or y2>=M)):
        return (x2,y2) # 이 애들이 바운드 넘었다.
    else:
        return False

def bfs(x1,y1,x2,y2):
    Q.append((x1,y1,x2,y2))
    cnt = 0

    while Q:
        cnt += 1
        if cnt > 10:
            return -1

        for _ in range(len(Q)):
            x1,y1,x2,y2 = Q.popleft()

            for a,b in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx1 = x1 + a
                ny1 = y1 + b
                nx2 = x2 + a
                ny2 = y2 + b

                outflag = isout(nx1,ny1,nx2,ny2)

                # 같아지면 둘다 같이 떨어진다.
                if nx1 == nx2 and ny1 == ny2:
                    continue

                if outflag == True: # 둘다 아웃
                    continue
                elif outflag == False: # 다 inbound -> 벽인지만 확인해봐야
                    wallflag = iswall(nx1, ny1, nx2, ny2)
                    if wallflag == True:  # 둘다 벽
                        continue
                    elif wallflag == False:  # 아무것도 벽이 아니다
                        Q.append((nx1,ny1,nx2,ny2))
                    else: # 하나만 벽이다.
                        if wallflag == (nx1,ny1):
                            Q.append((nx1-a, ny1-b, nx2, ny2))
                        else:
                            Q.append((nx1, ny1, nx2-a, ny2-b))
                else: # 하나만 아웃
                    if outflag == (nx1,ny1): # 얘가 아웃
                        if arr[nx2][ny2] != '#':
                            return cnt
                    else:
                        if arr[nx1][ny1] != '#':
                            return cnt


if __name__ == '__main__':
    N,M = map(int, input().split())
    arr = [list(input()) for _ in range(N)]
    vis1 = [[0]*M for _ in range(N)]
    vis2 = [[0]*M for _ in range(N)]
    balls = []
    Q = deque()
    for i in range(N):
        for j in range(M):
            if arr[i][j] == 'o':
                balls.append((i,j))
    print(bfs(balls[0][0],balls[0][1],balls[1][0],balls[1][1]))

caritas1996 3년 전 0

예제 5번은 한개가 3번째 줄에 도착한 후 나머지 1개가 왼쪽 혹은 오른쪽으로 굴러 떨어지게 돼서 3이 나오게 되는데요

3번째 줄에 위치한 동전은 양쪽에 벽이 있어서 움직이지 못하는 상태가 됩니다

나머지 1개가 아웃되는 순간 나머지 1개는 맵 안에 있으면서 벽이 아닌 곳에 있어야 한다고 생각하신 것 같은데

동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.

이 규칙때문에 이동하려는 위치(nx2, ny2)가 벽이므로 제자리에 위치해야해요.

해당 조건에서는 리턴하는 상황이면서 (nx2, ny2)가 inbound니까 굳이 벽인지 여부를 체크할 필요가 없을거 같아요.

...
else: # 하나만 아웃
    if outflag == (nx1,ny1): # 얘가 아웃
        if arr[nx2][ny2] != '#': # 조건이 이상해요
            return cnt
        else:
            if arr[nx1][ny1] != '#': # 조건이 이상해요
                return cnt

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

문제

문제

출처

ICPC

5번 케이스 안맞음, 바로 틀림

ebbunnim 3년 전 0

caritas1996 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말