[CodeTree] 코드트리 빵 - 삼성 SW 역량테스트 2022 하반기 오후 1번 문제

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

 

문제 분석

• NxN 격자에 1~M번의 사람이 존재하며, 1번 사람은 1초에, ..., M번 사람은 M초에 정확하게 각자의 베이스 캠프에서 목적지인 편의점으로 이동을 수행함. (포켓몬 빵 사러가는 듯)
• 한 턴에 총 3가지의 행동이 순차적으로 수행됨.
• 사람 이동
  • 격자에 있는 사람들은 모두 본인이 가고 싶은 편의점 방향을 향해 1칸 이동함.
  • 최단 거리로 이동해야하며, 이동 가능한 방법이 여러가지라면  ↑, ←, →, ↓ 의 우선 순위로 움직임.
  • 최단 거리란 현재 pos -> 목표 pos로 도달하기까지 최소 거리를 의미함.
• 편의점 도착
  • 이동하고 나서 원하는 목적지인 편의점에 도착했을 경우, 앞으로 해당 칸을 지나갈 수 없게 됨.
  • 격자에 있는 사람들이 모두 이동한 후에 지나갈 수 없음을 유의.
• 베이스캠프에 사람 추가
  • T분이고 T <= M인 상황이라면, T번째 사람은 내가 가고자하는 편의점과 가장 가까운 베이스캠프를 선택함.
  • 가장 가깝다는 의미는 사람 이동 시 언급한 최단 거리와 동일함.
  • 가까운 베이스캠프가 여러개라면 행이 작은, 열이 작은 우선순위에 맞게 베이스캠프를 선택함.
  • 이 때부터 해당 베이스캠프를 다른 사용자가 이동하지 못함.
• 몇 분이 지난 후에 모든 사람이 편의점으로 이동하는지 구하는 시뮬레이션 문제.

 

문제 접근

• 초기화 단계
  • 이동 가능한 좌표인지 여부를 판단하기 위한 field 배열 선언 (0/1 = 이동 가능, -1 = 이동 불가능)
  • 베이스 캠프와 편의점 정보를 저장할 배열 선언.
  • 편의점 정보의 경우, T분에 출발 할 사람이 가고자하는 목적지가 담겨있기 때문에 순서가 중요함.
  • 격자 위에 존재하는 사람의 (cur_x, cur_y, dest_x, dest_y)를 저장하기 위한 base_to_store 딕셔너리 선언.
• 사람 이동
  • 사람 이동의 경우 우선순위를 가지고 이동한다고 요구사항이 나와있기 때문에, 처음에는 4방향 중 유클리디언 거리가 가장 가까운, 그 중 우선순위에 맞는 방향을 선택하도록 로직을 구현함.
  • 위 풀이 방법의 경우 그리디적인 접근이며, 이동하는 방향이 항상 목적지까지 이동할 수 있음을 보장하지 않음.
  • 이 과정에서 시간을 굉장히 많이 소비했으며, 중요한 Point는 "목적지까지 이동 가능한 경로" 중 최단 경로임.
  • 격자 위 사람마다 각각 BFS + 우선순위 탐색을 수행하며 좌표를 갱신하는 작업 수행.
• 편의점 도착
  • 순차적으로 "방문하지 못함" 처리를 하는 것이 아닌, 동시에 처리해야하는 부분임.
  • 이 부분 또한 명확한 문제 분석을 수행하지 않음으로 인해 시간 허비가 발생함. 
  • 편의점에 도착한 사람의 목적지 정보를 wall_pos에 추가한 후, 한 번에 처리하도록 구현.
• 베이스캠프에 사람 추가
  • 이 또한 (가장 가까운, row가 작은, col이 작은) 우선 순위에 맞게 베이스캠프를 선정하기 때문에, BFS 알고리즘을 활용하여 작업 수행.
  • 여러 가지 후보 군이 존재할 경우, sort()를 수행하여 갱신하도록 구현.
• base_to_store 딕셔너리가 비어있을 경우, 탐색을 종료하도록 설정.

 

소스 코드

# define lib
from copy import deepcopy
from collections import deque

# set value from input
n, m = map(int, input().split())
direc = [(-1, 0), (0, -1), (0, 1), (1, 0)]
field, basecamp, store = [], [], []
for i in range(n):
    line = list(map(int, input().split()))
    for j in range(n):
        if line[j] == 1:
            basecamp.append((i, j))
    field.append(line)

for _ in range(m):
    x, y = map(int, input().split())
    store.append((x-1, y-1))

base_to_store, base_visit = dict(), [False]*len(basecamp)
turn = 0

while True:
    # move first
    new_base_to_store = dict()
    wall_pos = []
    for idx, (cx, cy, ex, ey) in base_to_store.items():
        paths = []
        dq = deque([(cx, cy, [])])
        visit = [[False]*n for _ in range(n)]
        visit[cx][cy] = True

        while dq:
            px, py, ppath = dq.popleft()
            if (px, py) == (ex, ey):
                paths = ppath
                break

            for didx, (dx, dy) in enumerate(direc):
                nx, ny = px+dx, py+dy
                if nx < 0 or nx >= n or ny < 0 or ny >= n or visit[nx][ny] or field[nx][ny] == -1:
                    continue
                visit[nx][ny] = True
                dq.append((nx, ny, ppath+[(nx, ny)]))
        
        nx, ny = paths[0]
        if (nx, ny) == (ex, ey):
            wall_pos.append((nx, ny))
        else:
            new_base_to_store[idx] = [nx, ny, ex, ey]

    for nx, ny in wall_pos:
        field[nx][ny] = -1

    # add new person
    if turn < m:
        dest_x, dest_y = store[turn]
        dq = deque([(dest_x, dest_y, 0)])
        visit = [[False]*n for _ in range(n)]
        visit[dest_x][dest_y] = True
        
        # find min dist basecamp
        _candits = []
        while dq:
            cx, cy, ccost = dq.popleft()
            if (cx, cy) in basecamp:
                _candits.append((cx, cy, ccost))
                continue

            for dx, dy in direc:
                nx, ny = cx+dx, cy+dy
                if nx < 0 or nx >= n or ny < 0 or ny >= n or visit[nx][ny] or field[nx][ny] == -1:
                    continue
                visit[nx][ny] = True
                dq.append((nx, ny, ccost+1))
        
        _candits.sort(key=lambda x: (x[2], x[0], x[1]))
        nx, ny, _ = _candits[0]
        field[nx][ny] = -1
        new_base_to_store[turn] = [nx, ny, dest_x, dest_y]

    turn += 1
    base_to_store = deepcopy(new_base_to_store)
    if not base_to_store:
        break


print(turn)

• 제출 횟수: 3회 (틀린, 오래걸린 이유를 문제 분석에 기재했습니다.)
• 풀이 시간: 100분