글 읽기 - 반례 스스로 찾았습니다, 그런데 어디를 고쳐야 하는건지 모르겠습니다ㅠ

choyj1127 1년 전 0

제 코드에서 틀린 반례는 아래와 같았습니다.

다른 여러 테스트는 잘 통과하는데, 어떤 부분이 잘못되어서 아래 예제가 틀리는 것일까요?

못 찾겠어서 도움 부탁드립니다..

10 10
##########
#RB....#.#
#..#.....#
#........#
#.O......#
#...#....#
#........#
#........#
#.......##
##########

ans = 10

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

'''
10 10
##########
#RB....#.#
#..#.....#
#........#
#.O......#
#...#....#
#........#
#........#
#.......##
##########

ans = 10
나의 제출 =
Traceback (most recent call last):
  File "C:\Users\SAMSUNG\PycharmProjects\Practice\main.py", line 75, in <module>
    print(shaking_board())
  File "C:\Users\SAMSUNG\PycharmProjects\Practice\main.py", line 59, in shaking_board
    if board[r_ny][r_nx] == 'O':
IndexError: list index out of range
'''
    
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

n, m = map(int, input().split())
board = [['.' for _ in range(m)] for _ in range(n)]
for i in range(n):
    row = input().rstrip()
    for j in range(m):
        board[i][j] = row[j]

r_y, r_x, b_y, b_x = -1, -1, -1, -1
for i in range(n):
    for j in range(m):
        if board[i][j] == 'R':
            r_y, r_x = i, j
            board[i][j] = '.'
        if board[i][j] == 'B':
            b_y, b_x = i, j
            board[i][j] = '.'


def shaking_board():
    global r_y, r_x, b_y, b_x

    q = deque([[r_y, r_x, b_y, b_x, 0]])
    while q:
        r_y, r_x, b_y, b_x, cnt = q.popleft()
        if cnt == 10:
            break
        for i in range(4):
            r_ny, r_nx = r_y, r_x
            b_ny, b_nx = b_y, b_x
            moving_r, moving_b = True, True  # 움직일 수 있는 상태인지 확인하는 변수

            flag = 0  # 1: 이동 후 빨간 구슬만 들어감/ 0: 별일없이 이동 완료/ -1: 이동 후 파란 구슬이 들어감
            while moving_r or moving_b:
                # 정지된 것이 아니라면 이동
                if moving_r:
                    r_ny, r_nx = r_ny + dy[i], r_nx + dx[i]
                if moving_b:
                    b_ny, b_nx = b_ny + dy[i], b_nx + dx[i]
                
                # 벽이거나 정지된 상대 구슬과 겹쳐진다면 이동 전으로 되돌아간 후, 정지한다.
                if board[r_ny][r_nx] == '#' or (not moving_b and r_ny == b_ny and r_nx == b_nx):
                    r_ny -= dy[i]
                    r_nx -= dx[i]
                    moving_r = False
                if board[b_ny][b_nx] == '#' or (not moving_r and r_ny == b_ny and r_nx == b_nx):
                    b_ny -= dy[i]
                    b_nx -= dx[i]
                    moving_b = False
                # 두 구슬이 겹쳐지는 상황을 막기 위한 코드
                if board[r_ny][r_nx] == '#' or (not moving_b and r_ny == b_ny and r_nx == b_nx):
                    r_ny -= dy[i]
                    r_nx -= dx[i]
                    moving_r = False
                
                # 빨간 구슬이 O를 만났다면 보드판 밖으로 놓고 행동을 정지한 후, 들어감을 표시한다.
                # 이후 파란 구슬 만날 가능성이 있으니 우선 상황 지켜보기
                if board[r_ny][r_nx] == 'O':
                    r_ny, r_nx = -1, -1
                    moving_r = False
                    flag = 1
                # 파란 구슬이 O를 만났다면 실패를 표시한 후, 반복문 탈출
                if board[b_ny][b_nx] == 'O':
                    flag = -1
                    break

            if flag == 1:  # 빨간 구슬만 무사히 잘 들어간 경우
                return cnt + 1
            # 승패없이 이동이 완료되었고, 최소 둘 중 하나 이상은 변동이 있었을 경우
            if flag == 0 and not (r_y == r_ny and r_x == r_nx and b_y == b_ny and b_x == b_nx):
                q.append([r_ny, r_nx, b_ny, b_nx, cnt+1])

    return -1


print(shaking_board())

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

문제

문제

출처

ICPC

반례 스스로 찾았습니다, 그런데 어디를 고쳐야 하는건지 모르겠습니다ㅠ

choyj1127 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말