글 읽기 - 위 & 아래로는 계속 가는디, 왼쪽 & 오른쪽으로는 한칸씩 밖에 안움직입니다.

rlarudgh2017 1년 전 0

안녕하세요, 고수님들. 잠시 시간내주시어 도움 좀 주십사하고 질문을 남겨봅니다.

이 문제는 BFS랑 시뮬레이션을 결합한 문제라고 생각해서 BFS 뼈대를 만들고 방향으로 이동할 때에만 쭈욱 가도록 했습니다.

while loop에 true를 걸고 벽에 부딪히거나 구멍으로 쏘옥 빠져버릴 때만 멈추고 아니면 갑니다.

그래서 분명히 제가 생각할적에는요, 어느 방향으로 움직이던간에 벽에 부딪힐 때까지 계속 움직여야 하구요...

예제들은 잘 동작하는데 반례

5 10
##########
#.#......#
##.......#
#OR..B.#.#
##########

정답7, 근데 4가 나옵니다.

이게 안되길래, 큐에 들어가는 값들을 쭉 출력해봤고, 지가 이 두 눈으로 똑똑이 봤습니다.

위, 아래로는 제가 생각하는 대로 한번에 쭈욱 잘 가는디, 왼쪽 오른쪽 갈적에는 요시미츠 담넘어가듯이 열받게 한칸씩만 찔끔찔끔 움직여댑니다.

오늘밤에 잠을 못이룰 것 같습니다. 제발 한번만 도와주시면 감사하겠습니다.

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
board = [[] for _ in range(n)]
for i in range(n):
    oneLine = input().rstrip()
    for j in range(m):
        board[i].append(oneLine[j])
        if oneLine[j] == 'R':
            ry, rx = i, j
        if oneLine[j] == 'B':
            by, bx = i, j

dy = [0, 0, -1, 1]
dx = [1, -1, 0, 0]

def bfs(ry, rx, by, bx):
    queue = deque([(ry, rx, by, bx, 0)])
    visited = [(ry, rx, by, bx)]
    while queue:
        ry, rx, by, bx, cnt = queue.popleft()
        if cnt > 10:
            return -1
        if board[ry][rx] == 'O':
            return cnt
        for i in range(4):
            nxtRY, nxtRX = ry, rx
            while True:
                nxtRY, nxtRX = nxtRY + dy[i], nxtRX + dx[i]
                if board[nxtRY][nxtRX] == '#':
                    nxtRY, nxtRX = nxtRY - dy[i], nxtRX - dx[i]
                    break
                if board[nxtRY][nxtRX] == 'O':
                    break
            
            nxtBY, nxtBX = by, bx
            while True:
                nxtBY, nxtBX = nxtBY + dy[i], nxtBX + dx[i]
                if board[nxtBY][nxtBX] == '#':
                    nxtBY, nxtBX = nxtBY - dy[i], nxtBX - dx[i]
                    break
                if board[nxtBY][nxtBX] == 'O':
                    break
            
            if board[nxtBY][nxtBX] == 'O':
                continue
            if nxtBY == nxtRY and nxtBX == nxtRX:
                if abs(nxtRY - ry) + abs(nxtRX - rx) < abs(nxtBY - by) + abs(nxtBX - bx):
                    nxtBY, nxtBX = nxtBY - dy[i], nxtBX - dx[i]
                else:
                    nxtRY, nxtRX = nxtRY - dy[i], nxtRY - dx[i]
            if (nxtRY, nxtRX, nxtBY, nxtBX) not in visited:
                visited.append((nxtRY, nxtRX, nxtBY, nxtBX))
                queue.append((nxtRY, nxtRX, nxtBY, nxtBX, cnt + 1))
                print((nxtRY, nxtRX, nxtBY, nxtBX, cnt + 1))
    return -1

print(bfs(ry, rx, by, bx))

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