[코드트리/Python] 코드트리의 빵

 

1. 코드트리의 빵 (골2)

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

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

 

문제

 

풀이

 

CODE

from collections import deque


def solution(n, m, board, stores):
    # 각 인원들의 현재 위치 정보를 저장하는 dictionary
    position = {}
    for i in range(1, m + 1):
        position[i] = (-1, -1)
    # 편의점 방분 여부를 나타내는 is_visit
    is_visit = [0] * (m + 1)
    is_visit[0] = 1  # index 맞춰주기 위해 0번 방문 처리
    # 방문 가능한 칸인지 나타내는 2차원 array cannot_visit
    cannot_visit = [[0 for _ in range(n)] for _ in range(n)]
    # 초 관리 변수 t
    t = 1

    # 자신의 위치에서 자신의 목표 편의점까지의 최단 거리 이동을 위한 이동 방향 구하기
    def bfs_find_the_shortest_route_to_store(x, y, user_num):
        visit_check_in_bfs = [[0 for _ in range(n)] for _ in range(n)]
        queue = deque([])
        queue.append((x, y, []))
        visit_check_in_bfs[x][y] = 1

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

        while queue:
            x, y, route = queue.popleft()

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                # 이동 시 방문 가능 여부 체크
                if 0 <= nx < n and 0 <= ny < n:
                    # 방문 가능 여부 체크
                    if not cannot_visit[nx][ny] and not visit_check_in_bfs[nx][ny]:
                        visit_check_in_bfs[nx][ny] = 1  # 방문 처리
                        # 편의점 발견 시
                        if nx == stores[user_num][0] and ny == stores[user_num][1]:
                            if len(route) == 0:
                                return i
                            else:
                                return route[0]
                        else:
                            queue.append((nx, ny, route + [i]))

    # 자신의 목표 편의점에서 제일 가까운 베이스캠프 구하기
    def bfs_find_the_nearest_basecamp(x, y):
        # 현재 x, y는 목표 편의점 위치
        visit_check_in_bfs = [[0 for _ in range(n)] for _ in range(n)]
        queue = deque([])
        queue.append((x, y))
        visit_check_in_bfs[x][y] = 1

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

        while queue:
            x, y = queue.popleft()

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                # 이동 시 방문 가능 여부 체크
                if 0 <= nx < n and 0 <= ny < n:
                    # 방문 가능 여부 체크
                    if not cannot_visit[nx][ny] and not visit_check_in_bfs[nx][ny]:
                        visit_check_in_bfs[nx][ny] = 1  # 방문 처리
                        # 베이스캠프 발견 시
                        if board[nx][ny] == 1:
                            return nx, ny
                        else:
                            queue.append((nx, ny))

    while 0 in is_visit:
        # 1. 격자의 모든 사람들이 모두 본인의 편의점으로 1칸 이동
        for i in range(1, m + 1):
            x, y = position[i]
            # 1-1. i번 째 사람이 격자에 있는 경우
            if x >= 0 and y >= 0 and not is_visit[i]:
                # 1-2. 현재의 좌표 상황에서 목표 편의점까지의 bfs 진행, 첫 번째 이동 경로 반환
                way = bfs_find_the_shortest_route_to_store(x, y, i)
                # 1-3. 최단 거리 이동을 위한 1칸 이동 수행
                if way == 0:
                    position[i] = (x - 1, y)
                elif way == 1:
                    position[i] = (x, y - 1)
                elif way == 2:
                    position[i] = (x, y + 1)
                elif way == 3:
                    position[i] = (x + 1, y)

        # 2. 만약 편의점에 도착한 경우 멈추고 해당 칸은 못가게 하기
        for i in range(1, m + 1):
            x, y = position[i]
            if stores[i][0] == x and stores[i][1] == y:
                is_visit[i] = 1
                cannot_visit[x][y] = 1

        # 3. 만약 t <= m 이라면
        if t <= m:
            # 3-1. stores[m]과 가장 가까운 베이스 캠프 찾기
            nx, ny = bfs_find_the_nearest_basecamp(stores[t][0], stores[t][1])
            # 3-2. position[t]를 베이스 캠프 좌표로 설정
            position[t] = nx, ny
            # 3-3. 해당 칸을 방문 불가 칸으로 설정
            cannot_visit[nx][ny] = 1

        # 1분간의 모든 해야할 일이 끝나면 초 증가
        t += 1

    # while문 탈출 후 t 출력
    print(t-1)


if __name__ == "__main__":
    # 입력
    n, m = map(int, input().split())
    board = []
    stores = {}
    # 입력: 격자 정보
    for _ in range(n):
        board.append(list(map(int, input().split())))
    # 입력: 1 ~ m번 사람의 목표 편의점 정보
    for i in range(1, m + 1):
        x, y = map(int, input().split())
        stores[i] = (x - 1, y - 1)
    solution(n, m, board, stores)

• 구현 & bfs
• 제출기록