코드트리 빵 (파이썬)

https://www.codetree.ai/training-field/frequent-problems/codetree-mon-bread

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 상좌우하 순서대로 dx, dy를 만들고 지도를 a에 저장한다

    베이스캠프 좌표는 base에 저장한다

2. 편의점의 좌표를 cu에 저장한다

3. 편의점의 좌표를 순서대로 불러와서, 가장 가까운 베이스캠프를 bfs로 찾는다

    ex에는 이동불가능한 좌표를 기록하고, 중복 탐색 방지를 위해 check_mov를 갱신하면서 탐색한다

    가장 가까운 베이스캠프를 찾으면 base_start에 저장한다

4. 문제의 조건대로 베이스캠프에서 편의점으로 이동하는 bfs를 구현한다

    check_mov는 각 사람마다의 해당 좌표 방문 여부를 저장한다 (각각의 사람 번호까지 해서 3차원 리스트)

    ex는 이동불가능한 좌표, check_end는 해당 인덱스번째 사람이 편의점으로 이동을 완료했는지 체크한다

5. 1번 사람이 베이스캠프에 위치하는 것부터 시작이므로 걸린 시간 cnt를 1, 추가한 사람 번호 idx를 1로 시작한다

    베이스좌표를 q에 추가하고 ex, check_mov를 갱신한다

6. 2번째 사람부터는 베이스 캠프에 위치시켜 ex, check_mov를 갱신한다

    다음 차례에 이동하므로 반복문 맨 마지막에서 q에 좌표를 추가한다

7. 문제의 조건대로 한 칸씩 이동하기 위해 현재 q의 길이를 하는 반복문을 포함한다

    불러온 idx 번째 사람이 이미 이동을 완료했으면 break (continue) 한다

8. bfs로 이동하면서 다음좌표가 이동가능한 편의점이면 ex와 check_end를 갱신한다

    이동가능한 빈칸이면 q에 추가한다

9. 모든 탐색이 끝났으면 (=check_end에 0이 없으면) 반복문을 break한다

import sys
from collections import deque

input = sys.stdin.readline
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
base = []
for i in range(n):
    for j in range(n):
        if a[i][j] != 0:
            base.append([i, j])

cu = [0] * m
for i in range(m):
    x, y = map(int, input().split())
    cu[i] = [x-1, y-1]

base_start = []
ex = [[0] * n for _ in range(n)]
for x, y in cu:
    q = deque()
    q.append([x, y])
    ex[x][y] = 1
    check_mov = [[0] * n for _ in range(n)]
    check_mov[x][y] = 1
    flag = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if check_mov[nx][ny] == 0 and ex[nx][ny] == 0:
                    if a[nx][ny] == 1:
                        ex[nx][ny] = 1
                        base_start.append([nx, ny])
                        flag = 1
                    else:
                        q.append([nx, ny])
                        check_mov[nx][ny] = 1
            if flag:
                break
        if flag:
            break

ex = [[0] * n for _ in range(n)]
check_mov = [[[0] * m for _ in range(n)] for _ in range(n)]
check_end = [0] * m
cnt, idx = 1, 1
q = deque()
bx, by = base_start[0][0], base_start[0][1]
q.append([bx, by, 0])
ex[bx][by] = 1
check_mov[bx][by][0] = 1
while q:
    if 0 < idx < m:
        bx, by = base_start[idx][0], base_start[idx][1]
        ex[bx][by] = 1
        check_mov[bx][by][idx] = 1
    qlen = len(q)
    cnt += 1
    for _ in range(qlen):
        x, y, i = q.popleft()
        if check_end[i] == 1:
            continue
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                if check_mov[nx][ny][i] == 0 and ex[nx][ny] == 0:
                    if nx == cu[i][0] and ny == cu[i][1]:
                        ex[nx][ny] = 1
                        check_end[i] = 1
                    else:
                        q.append([nx, ny, i])

    if 0 not in check_end:
        break
    if 0 < idx < m:
        q.append([bx, by, idx])
    idx += 1

print(cnt)