[Python][구현/BFS] 코드트리 빵 - 코드트리 삼성 기출

[문제]

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=1&pageSize=20

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

 

[알고리즘]

• 사람 모두 이동 (이미 도착한 사람이나, 아직 area에 들어오지 않은 사람 예외처리하기 중요 !)
  • BFS로 편의점까지의 가까운 거리 탐색. 
    • 가장 먼저 도착하였을 때가 가장 가까운 거리.
    • 가까운 거리가 여러개일 경우는, 상좌우하 순으로 bfs를 진행하면 저절로 상좌우하의 우선 순위를 가지고 가장 가까운 route를 찾을 수 있음
    • route 까지 큐에 저장하기
  • 이동 후, 이동한 칸이 편의점일 시, 따로 저장하기
• 도착한 곳이 편의점이 있다면, 2차원 배열인 area와, store 도착 여부 update 하기
• time이 M 보다 작을 시, 가까운 basecamp 찾기
  • 이 또한 bfs로. 지나치지 못한 곳 고려해야하기 때문. 

 

[느낀점 / 깨달은 점]

• 한방에 풀었다. 1시간 33분 걸렸다 !
• 편의점 도착 여부를 이동 중에 업데이트하지 말기. 모든 사람이 이동한 후에 Update하는 것 중요
• 그리고 문제 순서대로 푸는 것이 중요한 것 같다. 
  • 가까운 베이스캠프를 찾는 것이 사람마다 이동 초반에 한번 이루어지는 작업이라서 나는 초반에 사람 이동 함수보다 베캠 서치 함수를 먼저 실행하였는데 그렇게하면 못가는 곳(빨간곳)의 순서가 꼬이게 된다.
  • 그래서 사람 이동 함수 보다 나중에 베캠 서치 함수를 두는 것이 맞다. 문제에서 말하는 대로. 

 

[코드]

import sys
from collections import deque

def print_2d(a):
    for i in a:
        for j in i:
            print(j, end=' ')
        print()
    print('---')
def search_nearest_basecamp(n):

    i, j, _ = store_list[n]
    q = deque([])
    v = [[False for _ in range(N)] for _ in range(N)]
    q.append((i, j))

    while q :
        ii, jj = q.popleft()

        for d in range(4):
            iii = ii + dy[d]
            jjj = jj + dx[d]

            if iii < 0 or jjj < 0 or iii >=N or jjj >=N or v[iii][jjj]:
                continue
            if area[iii][jjj] == -1 :
                continue

            if area[iii][jjj] == 1 :
                people_info[n] = [iii, jjj, iii, jjj]
                area[iii][jjj] = -1
                return (iii, jjj)
            v[iii][jjj] = True
            q.append([iii, jjj])

def move_people():

    store_arrived = []

    for n in range(M):
        if store_list[n][2] or len(people_info[n]) == 0: ## 편의점에 도착했을 경우
            continue
        i, j, _, _ = people_info[n]
        q = deque([])
        v = [[False for _ in range(N)] for _ in range(N)]
        q.append((i, j, []))

        final_route = []
        is_break = False
        while q :
            ii, jj, route = q.popleft()

            for d in range(4):
                iii = ii + dy[d]
                jjj = jj + dx[d]

                if iii < 0 or jjj < 0 or iii >= N or jjj >= N or v[iii][jjj]:
                    continue
                if area[iii][jjj] == -1:
                    continue
                if iii == store_list[n][0] and jjj == store_list[n][1] :
                    is_break = True
                    route.append((iii, jjj))
                    final_route = route
                    break

                route_ = route[:]
                route_.append((iii, jjj))
                q.append((iii, jjj, route_))
                v[iii][jjj] = True

            if is_break :
                break
        if final_route[0][0] == store_list[n][0] and final_route[0][1] == store_list[n][1]  :
            store_arrived.append(n)

        people_info[n][0] = final_route[0][0]
        people_info[n][1] = final_route[0][1]
    return store_arrived

def update_store_arrived(store_arrived):
    for n in store_arrived:
        store_list[n][2] = True
        i, j = store_list[n][0], store_list[n][1]
        area[i][j] = -1

def is_all_arrived():
    for s in store_list :
        _, _, is_arrived = s
        if not is_arrived :
            return False
    return True

dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]

N, M = map(int, input().split())
area = [list(map(int, input().split())) for _ in range(N)]
store_list = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
    store_list[i][0] -=1
    store_list[i][1] -=1
    store_list[i].append(False)
people_info = [[] for _ in range(M)]
time = 0
while True :

    time +=1
    ## 사람 모두 이동
    store_arrived = move_people()
    ## 도착 편의점 정보 Update
    update_store_arrived(store_arrived)

    if time <= M :

        ## 베캠 서치 & 베캠으로 이동
        search_nearest_basecamp(time-1)

    ## 편의점 모두 도착인지 판별
    if is_all_arrived():
        break
print(time)