글 읽기 - 13460번 어디가 잘못 된 지 모르겠습니다. ㅠㅠ 가르쳐주세요

iviolin2003 1년 전 0

문제의 예제 6번

10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.##...#
#O..#....#
#########

이 미로를 넣으면 정답은 7인데

제 코드에선 8 이 나옵니다.

어디가 잘못되서 그런 값이 나오는지 아무리 찾아봐도 모르겠습니다.

다른 예제들은 답이 잘 나오구요

가르침을 주시면 감사하겠습니다

import sys
W, H = map(int, sys.stdin.readline().split())

maze = []

for _ in range(W):
    maze.append(sys.stdin.readline().strip())

dp = [[[[0 for _ in range(H)] for _ in range(W)] for _ in range(H)] for _ in range(W)]

foots = []

direct_x = [0, 0, -1, 1] # 우, 좌, 위, 아래
direct_y = [1, -1, 0, 0]

for i in range(W):
    for j in range(H):
        if maze[i][j] == "R":
            r_x = i
            r_y = j
        if maze[i][j] == "B":
            b_x = i
            b_y = j
        if maze[i][j] == "O":
            goal_x = i
            goal_y = j
            
def Going_Direct(x, y, dx, dy): # #또는 O만날 때 까지 이동
    num = 0
    while True:
        x += dx
        y += dy
        num += 1
        if maze[x][y] == "#":
            x -= dx
            y -= dy
            num -= 1
            return x, y, num
        elif maze[x][y] == "O":
            return x, y, num

def exit_maze(rx, ry, bx, by, foot):
    f = foot
    
    if foot >= 11: # 11번 이상 이동
        return
    elif rx == goal_x and ry == goal_y: # 도착점에 R구슬이 도착     
        foots.append(foot)
        return
    elif bx == goal_x and by == goal_y: # 도착점에 B구슬이 도착
        return
    
    if dp[rx][ry][bx][by] == 0: #이미 방문한 곳이면 탈출
        for i in range(4): 
            dp[rx][ry][bx][by] = 1
            r_to_x, r_to_y, n_r = Going_Direct(rx, ry, direct_x[i], direct_y[i]) # R구슬 이동
            b_to_x, b_to_y, n_b = Going_Direct(bx, by, direct_x[i], direct_y[i]) # B구슬 이동

            if r_to_x == goal_x and r_to_y == goal_y and b_to_x == goal_x and b_to_y == goal_y: # R,B 구슬 동시에 도착점에 도달했을 경우
                pass
            
            else:
                if r_to_x == b_to_x and r_to_y == b_to_y: # R, B 구슬이 같은 좌표에 도착했을 경우
                    if n_r > n_b: # R구슬이 더 많이 이동했을 경우(B구슬이 벽에 더 가까이 있음)
                        r_to_x -= direct_x[i] # R 구슬 한칸 전으로 이동
                        r_to_y -= direct_y[i] 
                        f += 1
                        exit_maze(r_to_x, r_to_y, b_to_x, b_to_y, f)
                        r_to_x -= (direct_x[i] * (n_r - 1)) # 이동했던 좌표가 도착점이 아닌 경우 다시 원래상태로 복구
                        r_to_y -= (direct_y[i] * (n_r - 1))
                        b_to_x -= (direct_x[i] * n_b)
                        b_to_y -= (direct_y[i] * n_b)
                        f -= 1
                        dp[rx][ry][bx][by] = 0 
                    elif n_r < n_b: # B구슬이 더 많이 이동했을 경우(R구슬이 벽에 더 가까이 있음)
                        b_to_x -= direct_x[i] # B 구슬 한칸 전으로 이동
                        b_to_y -= direct_y[i]
                        f += 1
                        exit_maze(r_to_x, r_to_y, b_to_x, b_to_y, f)
                        r_to_x -= (direct_x[i] * n_r) # 이동했던 좌표가 도착점이 아닌 경우 다시 원래상태로 복구
                        r_to_y -= (direct_y[i] * n_r)
                        b_to_x -= (direct_x[i] * (n_b - 1))
                        b_to_y -= (direct_y[i] * (n_b - 1))
                        f -= 1
                        dp[rx][ry][bx][by] = 0 
                else: # R, B구슬이 같은 좌표에 도착하지 않았을 경우
                    f += 1 
                    exit_maze(r_to_x, r_to_y, b_to_x, b_to_y, f)
                    r_to_x -= (direct_x[i] * n_r)
                    r_to_y -= (direct_y[i] * n_r)
                    b_to_x -= (direct_x[i] * n_b)
                    b_to_y -= (direct_y[i] * n_b)
                    f -= 1
                    dp[rx][ry][bx][by] = 0

        dp[rx][ry][bx][by] = 1 # 상 하 좌 우 이동후 도착점에 도착하지 못했을 경우 방문 표시

exit_maze(r_x, r_y, b_x, b_y, 0)

min_foot = []
for foot in foots:
    if foot != -1:
        min_foot.append(foot)

if len(min_foot) > 0:
    print(min(min_foot))
else:
    print(-1)

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

문제

문제

출처

ICPC

13460번 어디가 잘못 된 지 모르겠습니다. ㅠㅠ 가르쳐주세요

iviolin2003 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말