[코드트리][기출문제] 코드트리 빵

자료구조를 제외한 라이브러리 최대한 사용하지 않고 문제풀기 (필요하면 직접 코딩)

문제

코드트리 코드트리 빵

문제 풀이 및 회고

문제가 좀 헷갈리게 써져 있는듯(나만 그런가… 제공되는 테스트 케이스가 더 있었으면 좋았을텐데). 문제 좀 명확히 읽고 제출하자 귀찮아서 코드 if name == “main” 안했음 ㅋㄷㅋㄷ

코드(python)

from collections import deque

directions = [[-1,0], [0,-1], [0,1], [1,0]] # 방향 우선순위 순

n, m = map(int, input().split()) # 격자 크기 n, 사람 수 m
board = [[0]*(n+1)]
base_camp_num = 1
base_camps = {} # [base_camp_num] = (y, x) 
marts = {} # [num] = [y,x]
people = {} # [num] = [y, x]
done_people = set()
for i in range(1, n+1):
    line = [0] + list(map(int, input().split()))
    for j in range(1, n+1):
        if line[j] == 1:
            base_camps[base_camp_num] = (i,j)
            base_camp_num += 1
            #base_camps.add((i,j))
    board.append(line) # 격자. 0 - 빈공간, 1 - 베이스캠프

for i in range(1, m+1):
    marts[i] = list(map(int, input().split()))

def show_info():
    """
    격자와 사람, base_camp 정보 확인
    """
    for i in range(1, n+1):
        print(board[i][1:])
    print("base camps : ", base_camps)

    print("people : ")
    for k, v in people.items():
        print("k, (y,x) :", k, v)
    return None

#show_info()

def find_base_camp(t: int):
    """
    t 사람의 시작할 base_camp 찾기 (idx로 반환)
    """
    global marts, base_camps, board
    now_mart = marts[t]
    candidates_base_camps = []
    list_base_camps = base_camps.items()

    for k, base_camp in list_base_camps: # 베이스 캠프 후보군 중에
        info = find_minimum_root(t, base_camp)
        if info == None or board[base_camp[0]][base_camp[1]] == -1: # 갈 수가 없으면 패스
            continue
        candidates_base_camps.append([info[1], base_camps[k], k]) # 거리 , (y, x) 작은 순으로 정렬하기 위함
    candidates_base_camps.sort() # 정렬
    selected_base_camp = candidates_base_camps[0][2] # 선택할 base camp idx 찾기
    
    return selected_base_camp

def find_minimum_root(k, v):
    """
    people k가 v에서 움직일건데 v로 가는 root 중 "가장 짧은 거리"로 가는 "첫 방향" 찾기
    """
    global n, marts, directions
    dest = marts[k]
    q = deque() # y, x, direction, distance
    visited = [[0]*(n+1) for _ in range(n+1)]
    y, x = v
    visited[y][x] = 1
    for i in range(4):
        ny, nx = y+directions[i][0], x+directions[i][1]
        if [ny, nx] == dest:
            return [i, 1]

        if 1 <= ny <= n and 1 <= nx <= n and board[ny][nx] != -1 and visited[ny][nx] == 0:
            q.append((ny, nx, i, 1))
            visited[ny][nx] = 1

    while q:
        for _ in range(len(q)):
            y, x, d, dis = q.popleft()
            for i in range(4):
                ny, nx = y+directions[i][0], x+directions[i][1]
                if [ny, nx] == dest:
                    return [d, dis + 1]

                if 1 <= ny <= n and 1 <= nx <= n and board[ny][nx] != -1 and visited[ny][nx] == 0:
                    q.append((ny, nx, d, dis+1))
                    visited[ny][nx] = 1
    return None

def go_people():
    """
    도착하지 않은 사람들의 최단 경로 방향으로 한칸 이동
    """
    global people, done_people, board, directions, marts
    # 최단경로 찾아서 갈 방향 정하기
    for k, v in people.items():
        if v == None:
            continue
        
        info = find_minimum_root(k, v) # 가장 짧은 루트의 방향과 거리 정보 찾기
        d = info[0] # 방향 정보만 사용하면 됨
        people[k] = [v[0]+directions[d][0], v[1]+directions[d][1]] # people k의 다음 경로

    return None

t = 0
stop = -1 # 디버깅용
while True:
    t += 1 # 시간 트래킹

    # 1.
    go_people()

    # 2.
    # people k가 도착한 경우
    for k, v in people.items():
        if k not in done_people and people[k] == marts[k]:
            board[people[k][0]][people[k][1]] = -1
            people[k] = None
            done_people.add(k)

    # 3.
    if t <= m:
        # mart[t] - base_camps 가장 가까운 곳에 base_camp 정하기
        selected_base_camp = find_base_camp(t)
        board[base_camps[selected_base_camp][0]][base_camps[selected_base_camp][1]] = -1 # base_camp 시작하는 곳에서는 -1
        people[t] = base_camps[selected_base_camp] # 사람 위치 확인
        del base_camps[selected_base_camp] # 해당 base camp 제거
    
    # 모두 도착했는가
    if len(done_people) == m:
        break

    if stop == t:
        print("now time t : ", t)
        show_info()
        break
print(t)