2206-壁を破って移動

💡 メモリまたはタイムアウトのBFSの問題を考慮する必要がある

✨나의 방법 - 벽을 부쉈는지의 여부를 체크해서 같이 큐에 담아두자!

✨나의 방법 1. 3차원 배열 하나로 생성해서, 우선순위에 따라 숫자만 다르게 체크하면 되지 않을까!
✨나의 방법 2. 2차원 배열 하나로 생성해서 체크하자!
✨나의 방법 3. 2차원 배열 2개를 만들어서 2번과 같은 방식으로 체크하자!

1.3 D配列でチェック

from collections import deque
import sys

def bfs(target_x, target_y):
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    while q:
        x, y, cnt, chance = q.popleft()
        if x == target_x and y == target_y:
            return cnt
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if nx >= N or nx < 0 or ny >= M or ny < 0:
                continue
            if board[nx][ny] == 1:
                if chance == 0:
                    q.append((nx, ny, cnt+1,chance+1))
            elif board[nx][ny] == 0 and not visited[nx][ny][0]:
                if chance == 0:
                    visited[nx][ny][0], visited[nx][ny][1] = 1, 1
                elif chance == 1 and visited[nx][ny][1]:
                    continue
                else:
                    visited[nx][ny][1] = 1
                q.append((nx, ny, cnt+1, chance))
    return -1


if __name__ == "__main__":
    input = sys.stdin.readline
    N, M = map(int,input().split())
    board = [list(map(int,input()[:-1])) for _ in range(N)]
    visited = [[[0,0] for col in range(M)] for _ in range(N)]
    start, end = (0,0,1,0), (N-1,M-1)

    q = deque([])
    q.append(start)
    print(bfs(end[0],end[1]))

2.2 D配列でチェック

from collections import deque
import sys

def bfs(target_x, target_y, cnt = 0):
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    v[q[0][0]][q[0][1]] = 2

    while q:
        cnt += 1
        for _ in range(len(q)):
            x, y, break_wall = q.popleft()
            if x == target_x and y == target_y:
                return cnt
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if nx >= N or nx < 0 or ny >= M or ny < 0:
                    continue
                if not break_wall:
                    if not board[nx][ny]:
                        if v[nx][ny] in [0, -1]:
                            v[nx][ny] = 2
                            q.append((nx, ny, break_wall))
                    else:
                        q.append((nx, ny, break_wall + 1))
                else:
                    if not board[nx][ny] and not v[nx][ny]:
                        v[nx][ny] = -1
                        q.append((nx, ny, break_wall))
    return -1

if __name__ == "__main__":
    input = sys.stdin.readline
    N, M = map(int,input().split())
    board = [list(map(int,input()[:-1])) for _ in range(N)]
    v = [[0] * M for _ in range(N)] #2차원 배열 하나 생성!
    start, end = (0, 0, 0), (N-1, M-1)
    q = deque([])
    q.append(start)

    print(bfs(end[0],end[1]))

3.2つの2 D配列を作成してチェックする

from collections import deque
import sys

def bfs(tx, ty, c = 0):
    d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    v[q[0][0]][q[0][1]] = True
    while q:
        c += 1
        for _ in range(len(q)):
            x, y, b = q.popleft()
            if x == tx and y == ty:
                return c
                break
            for dx, dy in d:
                nx, ny = x + dx, y + dy
                if nx >= N or nx < 0 or ny >= M or ny < 0:
                    continue
                if not b:
                    if l[nx][ny] == '0':
                        if not v[nx][ny]:
                            v[nx][ny] = True
                            q.append((nx, ny, b))
                    else:
                        q.append((nx, ny, True))
                else:
                    if l[nx][ny] == '0' and not v_b[nx][ny]:
                        v_b[nx][ny] = True
                        q.append((nx, ny, b))
    return -1

if __name__ == "__main__":
    input = sys.stdin.readline
    N, M = map(int,input().split())
    l = [list(input()) for _ in range(N)]
    v, v_b = [[False] * M for _ in range(N)], [[False] * M for _ in range(N)]
    q = deque([])
    q.append((0, 0, False))

    print(bfs(N-1, M-1))