[Samsung] 2022-2 오후 1번 코드트리빵

March 27, 2023

[Samsung] 2022-2 오후 1번 코드트리빵

Question

Language: Python

Difficulty: Gold 2

해당 문제는 주어진 시뮬레이션 과정을 구현하면 되는 문제이다.

베이스캠프에서 편의점 방향으로 이동
편의점에 도달한 사람의 경우 해당 자리를 더 이상 접근하지 못하도록 방지
베이스캠프에 사람이 도착

베이스캠프 -> 편의점 이동

베이스캠프에서 편의점까지의 경로 중에서 최소 경로에 위치한 좌표를 찾기 위해 역으로 bfs을 실행한다. 편의점을 기준으로 bfs을 실행하여 각각의 좌표점에 대한 거리를 초기화 해서, 현재 위치 좌표의 상,우,좌,하 방향의 거리값을 비교해서 최소 거리값에 위치한 좌표로 이동한다.

queue=deque([(0,store_location[0],store_location[1])])
distances=[[inf]*n for _ in range(n)]

while queue:
    distance,row,col=queue.popleft()

    if distance > distances[row][col]:
        continue
    distances[row][col]=distance

    if (row,col)==current_location:
        continue
    
    for dir in range(4):
        next_row=row+dy[dir]
        next_col=col+dx[dir]

        #격자를 벗어난 경우
        if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
            continue
        
        #지나갈 수 없는자리
        if board[next_row][next_col] == -1:
            continue
        #거리가 짧은 경우에만 도달
        if distance + 1 < distances[next_row][next_col]:
            distances[next_row][next_col]=distance+1
            queue.append((distance+1,next_row,next_col))

candidates=[]
#해당 위치에서 다음 위치의 후보 찾기
for dir in range(4):
    next_row=current_location[0]+dy[dir]
    next_col=current_location[1]+dx[dir]

    #격자를 벗어난 경우
    if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
        continue
    candidates.append((distances[next_row][next_col],dir,next_row,next_col))

candidates.sort(key=lambda x: (x[0],x[1]))
return candidates[0][2],candidates[0][3]

편의점에 도달한 사람의 경우, 해당 자리를 더 이상 접근하지 못하도록 접근 방지 처리를 한다.

#편의점에 도달한 사람의 위치는 더 이상 다른 사람들이 방문하지 못하도록 한다.
number_of_person=0
while number_of_person < m and locations[number_of_person] != (-1,-1):
    #이전에 도착 처리를 하지 않은 사람 중에서 편의점에 도착한 경우 도착 처리를 진행한다.
    if not arrived[number_of_person] and locations[number_of_person]==stores[number_of_person]:
        board[stores[number_of_person][0]][stores[number_of_person][1]]=-1
        arrived[number_of_person]=True
        count_of_arrived+=1
    number_of_person+=1

편의점에서 가장 가까운 베이스캠프에 사람을 위치시킨다.

1번과 유사한 방식으로, 편의점을 기준으로 bfs을 동작시켜서 가장 가까운 베이스 캠프를 구한다.

queue=deque([(0,store_location[0],store_location[1])])
visited=[[False]*n for _ in range(n)]
parking_lots=[]
while queue:
    distance,row,col=queue.popleft()
    
    if visited[row][col]:
        continue
    visited[row][col]=True

    if board[row][col]==1:
        parking_lots.append((distance,row,col))

    for dir in range(4):
        next_row=row+dy[dir]
        next_col=col+dx[dir]
        
        #격자를 벗어난 경우
        if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
            continue

        #해당 자리가 이미 차지한 자리인 경우(베이스캠프, 편의점)
        if board[next_row][next_col] == -1:
            continue

        queue.append((distance+1,next_row,next_col))
        
#거리순, 행순, 열순으로 정렬해서 가장 첫번째 값을 반환
parking_lots.sort()

return parking_lots[0][1],parking_lots[0][2] 

Solution

from collections import deque
from math import inf

#주차장을 찾기 위한 bfs
def find_parking_lot(store_location):
    queue=deque([(0,store_location[0],store_location[1])])
    visited=[[False]*n for _ in range(n)]
    parking_lots=[]
    while queue:
        distance,row,col=queue.popleft()
        
        if visited[row][col]:
            continue
        visited[row][col]=True

        if board[row][col]==1:
            parking_lots.append((distance,row,col))

        for dir in range(4):
            next_row=row+dy[dir]
            next_col=col+dx[dir]
            
            #격자를 벗어난 경우
            if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                continue

            #해당 자리가 이미 차지한 자리인 경우(베이스캠프, 편의점)
            if board[next_row][next_col] == -1:
                continue

            queue.append((distance+1,next_row,next_col))
            
    #거리순, 행순, 열순으로 정렬해서 가장 첫번째 값을 반환
    parking_lots.sort()

    return parking_lots[0][1],parking_lots[0][2]        

#편의점 방향으로 이동하기 위한 함수
def move_to_store(store_location,current_location):
    queue=deque([(0,store_location[0],store_location[1])])

    distances=[[inf]*n for _ in range(n)]

    while queue:
        distance,row,col=queue.popleft()

        if distance > distances[row][col]:
            continue
        distances[row][col]=distance

        if (row,col)==current_location:
            continue
        
        for dir in range(4):
            next_row=row+dy[dir]
            next_col=col+dx[dir]

            #격자를 벗어난 경우
            if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                continue
            
            #지나갈 수 없는자리
            if board[next_row][next_col] == -1:
                continue
            #거리가 짧은 경우에만 도달
            if distance + 1 < distances[next_row][next_col]:
                distances[next_row][next_col]=distance+1
                queue.append((distance+1,next_row,next_col))
    
    candidates=[]
    #해당 위치에서 다음 위치의 후보 찾기
    for dir in range(4):
        next_row=current_location[0]+dy[dir]
        next_col=current_location[1]+dx[dir]

        #격자를 벗어난 경우
        if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
            continue
        candidates.append((distances[next_row][next_col],dir,next_row,next_col))

    candidates.sort(key=lambda x: (x[0],x[1]))
    return candidates[0][2],candidates[0][3]

def print_board():
    for row in board:
        print(*row)


def solution():
    global board
    time=0
    #각 사용자들의 베이스캠프 저장
    camps=[(-1,-1)] * m

    #각 사용자들의 위치 좌표 저장
    locations=[(-1,-1)] *m

    #도착한 사람들의 정보
    arrived=[False]*m
    count_of_arrived=0

    #모든 사용자들이 편의점에 도달할 때까지 반복 진행
    while count_of_arrived <m:

        #편의점 방향으로 이동
        number_of_person=0
        while number_of_person < m and locations[number_of_person] != (-1,-1):
            #아직 편의점에 도달하지 않은 경우에만 이동한다.
            if not arrived[number_of_person]:
                new_location=move_to_store(stores[number_of_person],locations[number_of_person])
                locations[number_of_person]=new_location

            number_of_person+=1
        
        #편의점에 도달한 사람의 위치는 더 이상 다른 사람들이 방문하지 못하도록 한다.
        number_of_person=0
        while number_of_person < m and locations[number_of_person] != (-1,-1):
            #이전에 도착 처리를 하지 않은 사람 중에서 편의점에 도착한 경우 도착 처리를 진행한다.
            if not arrived[number_of_person] and locations[number_of_person]==stores[number_of_person]:
                board[stores[number_of_person][0]][stores[number_of_person][1]]=-1
                arrived[number_of_person]=True
                count_of_arrived+=1
            number_of_person+=1

        #베이스 캠프 찾아서, 사용자를 위치 시키고, 해당 자리는 영구적으로 방문 제외 처리
        if time < m:
            parking_lot=find_parking_lot(stores[time])
            locations[time]=parking_lot
            camps[time]=parking_lot
            board[parking_lot[0]][parking_lot[1]]=-1
        time+=1
    print(time)

if __name__ == "__main__":
    n,m=map(int,input().split())
    board=[list(map(int,input().split())) for _ in range(n)]
    stores=[tuple(map(lambda x: int(x)-1,input().split())) for _ in range(m)]
    
    dy=[-1,0,0,1]
    dx=[0,-1,1,0]

    solution()

Twitter Facebook LinkedIn

Jehyun Jung

[Samsung] 2022-2 오후 1번 코드트리빵

[Samsung] 2022-2 오후 1번 코드트리빵

Question

Language: Python

Difficulty: Gold 2

Solution

공유하기

댓글남기기

참고

Typescript Module Issue

Changing Java Version in Linux

[BOJ] Q1725 히스토그램

[Programmers] Q176962 과제 진행하기