코드트리 빵(G2) 삼성 SW 역량테스트 2022 하반기 오후 1번 문제

 

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

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

코드트리에서 제공해주는 삼성 2022 하반기 오후 1번 문제이다. 삼성의 전형적인 그래프탐색을 이용한 시물레이션 문제이다.

일단 문제를 대략적으로 설명하자면 인기있는 빵을 구하기 위해 자신이 목표로 하는 편의점을 최단거리로 돌아다니는 문제이다. 문제만 들으면 뭐 그냥 BFS돌리면 되겠네 싶지만 그렇게 호락호락하지 않다. 우선 주어진 조건은 아래와 같다.

 

조건

빵을 원하는 사람 : m 

m번 사람은 m분에 각자 목표로 하는 편의점과 가장 가까운(최단거리) Base캠프에서 시작하며 가고자 하는 편의점은 모두 다르다.

 

1. 격자에 모든 인원은 본인이 가고 싶은 편의점 방향으로 1칸 움직일 수 있다

- 이때 최단거리로 움직이여야 하며 만약 최단거리가 여러개라면( ↑, ←, →, ↓)의 우선순위로 움직인다.

 

2. 편의점 도착 시 편의점에서 멈추며 해당 편의점은 못지나간다. 

- 위 조건은 격자안에 있는 모든 인원이 움직인 후에 발동이 된다.

 

3. 현재 시간이 t분이고 t<=m을 만족한다면 t번 사람은 자신이 가고싶어 하는 편의점과 가장 가까운 베이스캠프로 이동한다. 이 때 이동시간은 소요하지 않는다. 

- 이 때 이용한 베이스캠프로는 앞으로 지나가지 못한다.

 

문제 해결

위와 같이 주어진 조건들을 요약해서 하나씩 정리하면서 각각 조건에 맞는 알고리즘과 자료구조들을 생각해봤다.

 

1번 조건

- 격자에 모든 인원은 자신이 가고 싶은 편의점 방향으로 움직여야함 -> 시작 Queue를 이용해서 격자안에 인원들을 관리

- 자신의 위치부터 편의점 까지 최단거리 검색 -> BFS를 이용하여 자신의 위치부터 최단거리를 검색한 후 해당 경로에 맞게 이동

 

2번 조건

- 편의점 도착 시 편의점에서 멈추며 해당 편의점은 접근 금지 + 격자안에 모든 인원이 움직인 후에 발동 -> 도착 Queue를 이용하여 도착한 인원들을 한번에 업데이트

 

3번 조건

- 현재 시간이 t분이고 t<=m을 만족한다면 t번 사람은 출발 -> 대기자 Queue를 이용하여 조건에 맞게 한 명씩 격자위로 올리기

- 편의점과 가장 가까운 베이스캠프로 이동 -> 가고자 하는 편의점과 베이스캠프를 좌표를 이용하여 최단거리(BFS)탐색

- 이용한 베이스캠프는 앞으로 지나가지 못한다 -> 해당 베이스캠프 이동 불가 표시 후 베이스캠프 삭제

 

코드로 구현하기전에 미리 위와같이 정리를 하니 코드 구현은 그렇게 어렵지 않았다.(물론 중간중간 여러번 틀림)

 

위 처럼 정리한 형태를 구현한 틀은 아래와 같다. 

time = 0
while True:
    time+=1
    
    """ #step1
    격자에 있는 모든 인원은 본인이 가고 싶은 편의점 방향으로 1칸 움직인다.
    이 때 최단거리로 이동해야 하며 최단경로가 여러개인 경우 U L R D순으로 움직인다.
    """
    size = len(start)
    while size != 0:
        size-=1
        #-- 격자 안에 있는 인원을 하나 뽑고
        target_x, target_y, x, y = start.popleft()
        x, y = shortestPath(x, y, target_x, target_y) #-- 최단거리로 이동 후 
        
        #-- 목적지에 도착했다면 도착 Queue에 저장
        if x == target_x and y == target_y:
            # print("도착지 도착!!")
            finish.append([target_x, target_y])
        #-- 아직 도착 전이라면 다시 시작 Queue에 저장
        else:
            start.append([target_x, target_y, x, y])
        
    """ #step2
    편의점 도착 시 편의점에서 멈추며  (도착 queue로 넘김)
    
    (도착 Queue를 순회하면서 아래 로직을 수행하면 될듯)
    해당 편의점은 못지나가게 된다.(-1로 벽을 표시)    
    해당 로직은 격자에 있는 모든 인원이 움직인 후 발동한다.
    """
    while finish:
        target_x, target_y = finish.popleft()
        grid[target_y][target_x] = -1
    
    """ #step3
    현재 시간이 t분이고 t<=m를 만족한다면
    t번째 사람은 자신이 가고싶어 하는 편의점 가장 가까운 베이스 캠프로 이동한다(이동시간 소모 X)
    이 때부터는 해당 베캠은 사용이 불가능하다.
    """
    
    #-- 대기중인 사람 한 명을 꺼내옴
    if len(ready) != 0:
        i, target_x, target_y, x, y = ready.popleft()
    
        if time <= i:
            #== 자신이 가고 싶어하는 편의점 가강 가까운 베이스 캠프로 이동한다.
            x, y = shortestPathToBaseCamp(target_x, target_y)
            #-- 해당 베이스 캠프는 더 이상 사용이 불가
            grid[y][x] = -1

        #-- 가고싶은 편의점 위치 + 자신의 위치 전송
        start.append([target_x, target_y, x, y])
    
    if len(start) == 0:
        break
print(time)

 

가장 핵심적인 부분은 아래 3가지인것 같다.

 

1. 준비, 시작, 도착 3개의 Queue를 이용하여 인원들을 관리

2. 현재 위치부터 편의점까지 최단거리 계산, 최단경로 계산

3. 현재 편의점에서 가장 가까운 베이스 캠프 최단거리 계산

 

1번은 단순히 자료구조를 가져와서 사용하면 되니까 어렵지 않았다. 다만 2번 최단경로 계산 이 부분을 어떻게 구현해야할지 고민이 많았다.

최단 거리는 계산해봤어도 최단경로는 어떻게 계산했더라... 고민을 하다가 그냥 단순하게 최단 거리와함께 최단경로를 저장해주는 배열을 만들어서 역추적하는 방식으로 처리를 했다.

 

편의점부터 최단거리 및 최단 경로 계산 

일반적인 BFS탐색으로 최단 경로를 계산 하면서 목적지를 발견하면 그 목적지부터 최단 경로를 역추적하는 방식으로 구현했다.

최단 경로는 거리가 아닌 이동하는 방향을 저장해주는 방식으로 구현했다.

def shortestPath(X, Y, target_x, target_y):
    queue = deque()
    distance = [[INF for _ in range(N)] for _ in range(N)]
    trace = [[INF for _ in range(N)] for _ in range(N)]
    
    queue.append([X, Y])
    distance[Y][X] = 0
    trace[Y][X] = -2
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            flag = False
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < N and 0 <= ny < N and distance[ny][nx] == INF and grid[ny][nx] != -1:
                distance[ny][nx] = distance[y][x] +1
                trace[ny][nx] = i
                if nx == target_x and ny == target_y:
                    flag = True
                    break
                queue.append([nx, ny])
        if flag == True:
            break
    #-- 최단 경로 추적
    prev_x = target_x
    prev_y = target_y
    

    while True:
        if trace[prev_y][prev_x] == -2:
            break
        dir = trace[prev_y][prev_x]
        if dir == 0:
            prev_y +=1        
        elif dir == 1:
            prev_x+=1
        elif dir == 2 :
            prev_x-=1
        elif dir == 3:
            prev_y -=1
    
    return X+dx[dir], Y+dy[dir]

 

편의점과 가장 가까운 베이스캠프 

 

가장 가까운 베이스캠프같은 경우는 마찬가지로 BFS로 편의점부터 모든 최단거리를 계산 한 후에 후보로 들어갈 수 있는 모든 베이스캠프들에 대한 최단거리를 리스트에 넣어준 후에  값 -> 더 작은 y -> 더 작은 x 값을 기준으로 정렬을 해준 뒤 최단 경로 베이스캠프를 삭제하는 방식으로 정리했던 로직을 그대로 코드로 구현했다.

def shortestPathToBaseCamp(X, Y):
    queue = deque()
    distance = [[INF for _ in range(N)] for _ in range(N)]
    
    queue.append([X, Y])
    distance[Y][X] = 0
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < N and 0 <= ny < N and distance[ny][nx] == INF and grid[ny][nx] != -1:
                distance[ny][nx] = distance[y][x] +1
                queue.append([nx, ny])
    
    shortestBase = []
    for basecamp in basecampList:
        x, y = basecamp
        shortestBase.append([distance[y][x], x, y])
    shortestBase.sort(key=lambda x : (x[0], x[2], x[1])) #-- 값 -> 같으면 더 작은 y 같으면 더 작은 x
    
    #-- 해당 베이스 캠프 삭제
    for basecamp in basecampList:
        if shortestBase[0][1] == basecamp[0] and shortestBase[0][2] == basecamp[1]:
            basecampList.remove(basecamp)
    return shortestBase[0][1], shortestBase[0][2]

 

 

위와 같이 3개의 조건들을 잘 조합해서 구현하니 무리 없이 통과했다!

 

 

전체 코드는 아래 깃허브에서 확인 가능하다!

https://github.com/junyong1111/codetree-TILs/tree/main/240403/%EC%BD%94%EB%93%9C%ED%8A%B8%EB%A6%AC%20%EB%B9%B5

codetree-TILs/240403/코드트리 빵 at main · junyong1111/codetree-TILs