[코드트리] 숫자가 가장 큰 인접한 곳으로 동시에 이동 - 파이썬

숫자가 가장 큰 인접한 곳으로 동시에 이동

문제

https://www.codetree.ai/missions/2/problems/move-to-max-adjacent-cell-simultaneously?&utm_source=clipboard&utm_medium=text

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

 

코드

• 위치 저장을 위해서 딕셔너리 사용
• max_value를 사용해 가장 큰 값이 있는 곳으로 이동
• 새로운 위치로 구슬을 업데이트하고, 하나만 존재할 수 있도록 구현

n, m, t = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

marble = []
for _ in range(m):
    r, c = map(int, input().split())
    marble.append((r-1, c-1))  # 0-indexed로 저장

dx = [-1, 1, 0, 0]  # 상, 하, 좌, 우
dy = [0, 0, -1, 1]

for _ in range(t):
    # 다음 위치 저장을 위한 딕셔너리
    next_position = {}
    
    # 모든 구슬 이동
    for r, c in marble:
        max_value = -1
        next_r, next_c = r, c
        
        for i in range(4):
            nr, nc = r + dx[i], c + dy[i]
            
            if 0 <= nr < n and 0 <= nc < n:
                if graph[nr][nc] > max_value:
                    max_value = graph[nr][nc]
                    next_r, next_c = nr, nc
        
        # 이동하려는 위치를 저장
        if (next_r, next_c) in next_position:
            next_position[(next_r, next_c)] += 1
        else:
            next_position[(next_r, next_c)] = 1
    
    # 새로운 위치로 구슬 업데이트, 충돌 처리
    new_marble = []
    for position, count in next_position.items():
        if count == 1:  # 구슬이 하나만 있는 경우에만 추가
            new_marble.append(position)
    
    marble = new_marble

# 남아있는 구슬의 수 출력
print(len(marble))