글 읽기 - BFS로 한번 풀어봤는데 계속 틀렸습니다.가 나옵니다. 조언 부탁드립니다.

iviolin2003 1년 전 0

해당 문제를 BFS로 구현해보려 하고 있습니다.

다만 계속 틀렸습니다.가 뜨는데 도저히 어디서 틀린 것인지 1도 모르겠습니다...

조언 부탁드립니다.

import sys
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(200000)

input = sys.stdin.readline
INF = sys.maxsize
N = int(input())
maze = []
result_f = INF
no_search_f = 0
move_tile = 0
is_goal = False
last_tile = 0
width = 2 * N

for line in range(1, N + 1): # 문제에서 제공된 정보들을 maze 변수에 저장
    if line % 2 == 0:
        maze.append([0])
        for _ in range(N - 1):
            maze[line - 1].extend(list(map(int, input().strip().split())))
        maze[line - 1].extend([0])
    else:
        maze.append([])
        for i in range(N):
            maze[line - 1].extend(list(map(int, input().strip().split())))

visit = [INF] * ((N ** 2) - (N // 2) + 1) # 총 타일의 개수만큼 visit 생성
visit[1] = 1
mark_visit = defaultdict(int) # 경로 출력을 위한 변수

def bfs(ly, lx, ry, rx, f, now_tile):
    global move_tile
    global move
    global result_f
    global is_goal
    global last_tile
    global no_search_f

    q = deque()
    q.append((ly, lx, ry, rx, f, now_tile))

    while q:
        ly, lx, ry, rx, f, now_tile = q.popleft()
        
        if (ry, rx) == (N - 1, width - 1): # 마지막 칸에 도착
            return f, now_tile

        is_search = False # 해당 칸에서 이동할 수 있는 칸의 유무 판별

        f += 1

        for dy, dx in ((-1, 0), (1, 0), (0, -1)): # 해당 타일의 좌측 칸에서 이동할 수 있는 타일 검색
            ny = ly + dy
            nx = lx + dx

            tiles = (ny * N) - (ny // 2) + ((nx - 1) // 2) + 1 # 이동할 타일의 넘버링 구하기

            if 0 <= ny < N and 0 <= nx < width and maze[ly][lx] == maze[ny][nx] and visit[tiles]> f: # 이동할 수 있는 칸이 있다면 변수들 갱신
                visit[tiles] = f
                
                mark_visit[tiles] = now_tile
                is_search = True
                q.append((ny, nx - 1, ny, nx, f, tiles))

        for dy, dx in ((-1, 0), (1, 0), (0, 1)): # 해당 타일의 우측 칸에서 이동할 수 있는 타일 검색
            ny = ry + dy
            nx = rx + dx

            tiles = (ny * N) - (ny // 2) + (nx // 2) + 1 # 이동할 타일의 넘버링 구하기

            if 0 <= ny < N and 0 <= nx < width and maze[ry][rx] == maze[ny][nx] and visit[tiles] > f: # 이동할 수 있는 칸이 있다면 변수를 갱신
                visit[tiles] = f

                mark_visit[tiles] = now_tile
                is_search = True
                q.append((ny, nx, ny, nx + 1, f, tiles))
        
        if not is_search: # 이동할 수 있는 칸이 없었다면 근처의 가장 큰 tile의 넘버링 구하기
            for dy, dx in ((1, 1), (1, -1), (0, 2)):
                ny = ly + dy
                nx = lx + dx

                tiles = (ny * N) - (ny // 2) + (nx // 2) + 1
                
                if 0 <= ny < N and 0 <= nx < width and maze[ny][nx] != 0:
                    if move_tile < tiles: # 현재 저장되어 있는 가장 큰 타일의 넘버링보다 더 큰 타일로 이동할 수 있다면 변수 갱신
                        move_tile = tiles
                        last_tile = now_tile
                        no_search_f = f - 1
    return no_search_f, last_tile
        
move_tile = 0
move = []
answer_f, answer_tile = bfs(0, 0, 0, 1, 1, 1)

# 정답 출력
print(answer_f)

temp = []
while answer_f:
    temp.append(answer_tile)
    answer_tile = mark_visit[answer_tile]
    answer_f -= 1

print(*temp[::-1])

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

문제

문제

출처

ICPC

BFS로 한번 풀어봤는데 계속 틀렸습니다.가 나옵니다. 조언 부탁드립니다.

iviolin2003 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말