[코드트리 | 삼성] 코드트리 빵

문제 개요

• 사람들
  • t번 사람은 t분에 자신이 가고싶은 편의점과 최단거리에 있는 베이스캠프에 들어감
    • 가장 가까운 베캠이 여러개이면 행이 작은 곳으로 , 행이 같으면 열이 작은 곳으로 들어감
    • 베이스캠프에 들어가는 데에는 시간이 소유되지 않음
    • 베이스캠프에 사람이 들어가면 그 이후로 다른 사람들은 해당 베이스캠프를 지나갈 수 없음
    • 격자에 있는 사람들이 모두 이동하고 해당 칸을 지날 수 없음
  • 가고 싶은 편의점 방향을 향해서 1칸 움직임
    • 최단거리로 움직임
    • 상, 좌, 우, 하 순으로 움직임
  • 편의점 도착
    • 해당 편의점에서 멈춤
    • 다른 사람들은 해당 편의점을 지나갈 수 없음
    • 격자에 있는 사람들이 모두 이동하고 해당 칸을 지나갈 수 없게 됨

문제를 위와 같이 정리할 수 있다.

풀이과정, 방향

함수는 들어갈 베이스캠프 결정/사람 이동 두 가지로 나누었다.
최단거리로 이동해야 하기 때문에 매 시점 BFS를 돌려서 최단경로를 구한 후 한 칸 이동하는 방향으로 움직여야 했다. 따라서, BFS 수행 시 경로를 기억해두도록 queue에 같이 경로 list를 넣었다.

코드

from collections import deque

#n*n 격자, m명의 사람
n, m = map(int, input().split())

town = []
stores = []
people = []
not_arrived = m

for i in range(n):
    town.append(list(map(int, input().split())))

for i in range(m):
    a,b = map(int, input().split())
    stores.append((a-1,b-1))
    people.append([-1,-1])

# -1: 지나갈 수 없는 칸
# 베이스 캠프에 들어간 이후, 편의점에 도착한 이후 베이스 캠프와 편의점이 해당하는 칸은 지나갈 수 없음

d = [(-1, 0), (0, -1), (0, 1), (1, 0)]

def find_basecamp(p):
    sy, sx = stores[p]

    q = deque()
    q.append((sy, sx))

    visited = [[False]*n for _ in range(n)]
    visited[sy][sx]=True
    while q:
        cy, cx = q.popleft()

        for dy, dx in d:
            ny = cy+dy
            nx = cx+dx

            if 0<=ny<n and 0<=nx<n:
                if visited[ny][nx]:
                    continue
                if town[ny][nx]==-1:
                    continue
                if town[ny][nx]==1:
                    people[p]=[ny, nx]
                    # town[ny][nx]=-1 사람들이 모두 이동한 뒤에 해당 칸을 지나갈 수 없어짐
                    cannotgo.append([ny, nx])
                    return [ny, nx]
                visited[ny][nx]=True
                q.append((ny, nx))

    print('something wrong!')


def person_move(p):
    global not_arrived
    py, px = people[p]
    sy, sx = stores[p]

    q = deque()
    q.append((py, px, [0,0]))

    visited = [[False]*n for _ in range(n)]
    visited[py][px]=True

    while q:
        cy, cx, first_step = q.popleft()

        for dy, dx in d:
            ny = cy+dy
            nx = cx+dx

            if 0<=ny<n and 0<=nx<n:
                if visited[ny][nx]: continue
                if town[ny][nx]==-1: continue
                if cy==py and cx==px:
                    if ny==sy and nx==sx:
                        not_arrived-=1
                        people[p] = [-1, -1] #도착
                        cannotgo.append([ny, nx])
                        return True
                    else:
                        visited[ny][nx]=True
                        q.append((ny, nx, [ny, nx]))
                else:
                    if ny==sy and nx==sx:
                        people[p] = first_step
                        return True
                    else:
                        visited[ny][nx]=True
                        q.append((ny, nx, first_step))
    return False




t = 0
cannotgo = [] # 폐쇄된 칸 리스트
while not_arrived>0:

    # step 1,2 : 격자 위에 있는 모든 사람들 움직임
    for i in range(m):
        if people[i][0]!=-1:
            person_move(i)

    # step0: cannotgo 리스트에 있는 칸 폐쇄
    while cannotgo:
        y,x = cannotgo.pop()
        town[y][x]=-1


    # step 3: 
    if t < m:
        find_basecamp(t)

    while cannotgo:
        y,x = cannotgo.pop()
        town[y][x]=-1

    t+=1

print(t)

느낀점

BFS를 매번 시행해서 경로를 얻는 게 신기했다. 일반적으로 행/열의 차를 각각 구해 절대값을 씌우는 형태로 거리를 구하는데, 이 문제에서는 최단경로를 거리로 두어서 이동해야 했다. 생각보다 비교적 수월하게 풀었음.