글 읽기 - 로직 방식이 궁금합니다.

hena_42 2년 전 0

queue의 사이즈만큼 돌면 밤 낮 바뀌게 했고, wall은 현재 깨트린 벽의 개수입니다.

아예 로직이 틀린건지 이 방식으로 불가능한지 알고 싶습니다.

import sys
import heapq
from collections import deque
input = sys.stdin.readline
n, m, k = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
visited = [[[-1] * (k + 1) for _ in range(m)] for _ in range(n)]
for i in range(k + 1):
    visited[0][0][i] = 1

graph = []
for i in range(n):
    graph.append(list(map(str,input().rstrip())))
# print(visited)
def BFS():
    
    #flag: True-아침, False-저녁
    flag = True
    #1: 현재 벽 파괴수, 2: x좌표, 3: y좌표
    queue = deque([[0, 0, 0]])
    # heapq.heappush(queue, )

    while queue:
        for _ in range(len(queue)):
            # wall, x, y = heapq.heappop(queue)
            wall, x, y = queue.popleft()
            # print(wall, x, y)
            if x == n - 1 and y == m - 1:
                print(visited[x][y][wall])
                return
            if flag:#아침
                # print("morning")
                for i in range(4):
                    newX, newY = x + dx[i], y + dy[i]
                    if newX < 0 or newX >= n or newY < 0  or newY >= m:
                        continue
                    if wall < k and graph[newX][newY] == '1' and visited[newX][newY][wall + 1]== -1:
                        # print("wall")
                        visited[newX][newY][wall + 1] = visited[x][y][wall] + 1
                        # heapq.heappush(queue,[wall + 1, newX, newY])
                        queue.append([wall + 1, newX, newY])
                    if wall < k + 1 and graph[newX][newY] == '0' and visited[newX][newY][wall] == -1:
                        # print("no wall")
                        visited[newX][newY][wall] = visited[x][y][wall] + 1
                        # heapq.heappush(queue,[wall, newX, newY])
                        queue.append([wall, newX, newY])
            else:#저녁
                # print("night")
                for i in range(4):
                    newX, newY = x + dx[i], y + dy[i]
                    if newX < 0 or newX >= n or newY < 0  or newY >= m:
                        continue
                    if wall < k and graph[newX][newY] == '1' and visited[newX][newY][wall + 1]== -1:
                        # print("wall")
                        visited[x][y][wall] = visited[x][y][wall] + 1
                        # heapq.heappush(queue,[wall, x, y])
                        queue.append([wall, x, y])
                    if wall < k + 1 and graph[newX][newY] == '0' and visited[newX][newY][wall] == -1:
                        # print("no wall")
                        visited[newX][newY][wall] = visited[x][y][wall] + 1
                        queue.append([wall, newX, newY])
                        # heapq.heappush(queue,[wall, newX, newY])
            # print(queue)
        flag = not flag
    print(-1)
    return
BFS()

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

문제

문제

출처

ICPC

로직 방식이 궁금합니다.

hena_42 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말