[코드트리/삼성SW역량테스트] 코드트리 빵 (Python)

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

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

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:51:57

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

구현을 진행하되, 문제 전반에서 사용하는 거리는 "이동 가능한 경로중 최소 경로"를 전제로 한다. 따라서 이러한 최소 경로를 반환하는 BFS를 적용할 필요가 있다. 이외에는 각 처리 순서를 체례대로 수행하는 점만 주의하도록 한다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline

dr = [-1, 0, 0, 1]
dc = [0, -1, 1, 0]
MAX = float('inf')

N, M = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]
movable = [[True]*N for _ in range(N)]

def distance(r, c, tr, tc) :
    q = deque([(r, c, 0)])
    visited = [[False]*N for _ in range(N)]
    visited[r][c] = True

    while q :
        r, c, d = q.popleft()
        if (r, c) == (tr, tc) :
            return d
        for i in range(4) :
            ar, ac = r + dr[i], c + dc[i]
            if -1 < ar < N and -1 < ac < N and movable[ar][ac] and not visited[ar][ac] :
                visited[ar][ac] = True
                q.append((ar, ac, d+1))
    return MAX

class Person() :
    def __init__(self, r, c, idx) :
        self.tr = r
        self.tc = c
        self.r = -1
        self.c = -1
        self.idx = idx
        self.started = False
        self.arrived = False

    def basecamp_init(self, t) :
        if self.started or t < self.idx :
            return
        br, bc, bdist = -1, -1, MAX
        for i in range(N) :
            for j in range(N) :
                if maps[i][j] == 1 :
                    dist = distance(i, j, self.tr, self.tc)
                    if dist < bdist :
                        br, bc, bdist = i, j, dist
        maps[br][bc] = 0
        movable[br][bc] = False
        self.started = True
        self.r, self.c = br, bc

    def move(self) :
        if not self.started or self.arrived :
            return
        
        br, bc, bdist = -1, -1, MAX
        for i in range(4) :
            r, c = self.r + dr[i], self.c + dc[i]
            if -1 < r < N and -1 < c < N and movable[r][c] :
                dist = distance(r, c, self.tr, self.tc)
                if dist < bdist :
                    br, bc, bdist = r, c, dist
        
        self.r, self.c = br, bc

    def is_arrived(self) :
        if self.arrived :
            return 1
        if (self.r, self.c) == (self.tr, self.tc) :
            self.arrived = True
            movable[self.r][self.c] = False
            return 1
        return 0

people = list()
for i in range(M) :
    r, c = map(int, input().split())
    people.append(Person(r-1, c-1, i))

t = 0
while True :
    cnt = 0
    for i in range(M) :
        people[i].move()
    for i in range(M) :
        cnt += people[i].is_arrived()
    for i in range(M) :
        people[i].basecamp_init(t)
    if cnt == M :
        print(t+1)
        break
    t += 1

풀이 완료!