[백준_20057]마법사 상어와 토네이도 with Python

백준(BOJ) "삼성 SW 역량 테스트 기출 문제" 문제집: 마법사 상어와 토네이도(골드 4)

문제 출처: www.acmicpc.net/problem/20057

20057번: 마법사 상어와 토네이도

1. 알고리즘

• 격자의 가운데 칸(N//2, N//2)에서 토네이도의 이동 시작
• 토네이도 한 방향에서의 이동 횟수를 저장한 리스트와 비교하는 방법으로 각 회전 당 이동 횟수, 방향 제한
  • 한 방향에서의 이동 횟수는 순서대로 다음과 같은 규칙성을 보임. (1, 1, 2, 2, 3, 3, ..., N-2, N-2, N-1, N-1, N-1)
    • 1, 1, 2, 2, ..., N-1, N-1, N의 리스트를 생성. 토네이도가 (0, 0)에 도착했을 때를 종료조건으로 설정하면 위의 규칙에 맞게 동작함.
  • 현재 이동 횟수가 현재 방향에서의 이동횟수와 일치
    • 현재 이동횟수 초기화, 방향 전환, 방향 전환에 따른 다음 방향에서의 이동횟수로 리스트 인덱스 증가
• 토네이도의 다음 위치 모래의 양을 방향에 따른 모래 이동 방향으로 이동
  • 각 이동 %에 맞는 양을 소숫점 이하 버림으로 계산
  • 이동하는 칸의 범위를 확인
    • 범위 내부라면 기존 모래와 합쳐줌
    • 범위 밖이라면 sand_lose 변수에 값을 더해줌
  • 이때, 이동하는 모래의 양을 전부 더하여 마지막에 a로 이동할 모래의 양을 계산
• 토네이도 위치 갱신, 이동 횟수 +1
• 반복문 수행 이후, sand_lose 출력

 

2. 유의 사항

• 모래의 %이동량은 토네이도의 이동 방향에 따라 회전함
• α는 %가 정해진 모래가 전부 이동한 나머지 값이어야 함.
  • 이동하는 모래의 %를 계산하면 α는 55%이지만, %가 정해진 모래의 이동량이 버림이기 때문에, 55%의 모래와 전부 이동하고 남은 모래의 양에는 차이가 있을 수 있음

 

3. 어려웠던 점, 해결 방법

 

4. 소스 코드

상세 코드 설명은 주석

import sys
 
 
if __name__=="__main__":
    N = int(*map(int, sys.stdin.readline().split()))
    sand = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
 
    #토네이도 시작점(격자의 가운데 칸)
    r, c = N//2, N//2
 
    #토네이도의 방향 별 이동 횟수 리스트
    tornado_rotation_time = [i//2+1 for i in range(N*2-1)]
    #토네이도의 이동 방향(좌, 하, 우, 상)
    tornado_direction = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    #각 토네이도의 이동 방향에 따른 모래 이동 비율(행, 열, 비율)
    sand_move_direction = [[(-1, 1, 0.01), (1, 1, 0.01), (-2, 0, 0.02), (2, 0, 0.02), (-1, 0, 0.07), (1, 0, 0.07),
                  (-1, -1, 0.1), (1, -1, 0.1), (0, -2, 0.05), (0, -1, 0.55)],
                 [(-1, -1, 0.01), (-1, 1, 0.01), (0, -2, 0.02), (0, 2, 0.02), (0, -1, 0.07), (0, 1, 0.07),
                  (1, -1, 0.1), (1, 1, 0.1), (2, 0, 0.05), (1, 0, 0.55)],
                 [(-1, -1, 0.01), (1, -1, 0.01), (-2, 0, 0.02), (2, 0, 0.02), (-1, 0, 0.07), (1, 0, 0.07),
                  (-1, 1, 0.1), (1, 1, 0.1), (0, 2, 0.05), (0, 1, 0.55)],
                 [(1, -1, 0.01), (1, 1, 0.01), (0, -2, 0.02), (0, 2, 0.02), (0, -1, 0.07), (0, 1, 0.07),
                  (-1, -1, 0.1), (-1, 1, 0.1), (-2, 0, 0.05), (-1, 0, 0.55)]]
    
    rotation_time, move_time, direction = 0, 0, 0
    sand_lose = 0
    while (r, c) != (0, 0):
        
        #현재 이동 횟수, 이동해야할 횟수 비교
        if move_time == tornado_rotation_time[rotation_time]:
            move_time = 0
            direction += 1
            direction %= 4
            rotation_time += 1
        
        nr = r + tornado_direction[direction][0]
        nc = c + tornado_direction[direction][1]
        
        #이동할 모래
        y = sand[nr][nc]
        
        total_move_sand = 0
        #모래 이동 방향, 비율에 따라 모래 이동
        for dx, dy, percentage in sand_move_direction[direction]:
            #α인 경우 예외 처리
            if percentage == 0.55:
                move_sand = y-total_move_sand
            else:
                move_sand = int(y*percentage)
 
            move_sand_r, move_sand_c = nr + dx, nc + dy
            total_move_sand += move_sand
            
            #모래 이동 범위가 격자 범위 내인지 확인
            if 0<=move_sand_r<N and 0<=move_sand_c<N:
                sand[move_sand_r][move_sand_c] += move_sand
            else:
                sand_lose += move_sand
    
        #토네이도 좌표 갱신, 이동 횟수+1
        r, c = nr, nc
        move_time += 1
 
    print(sand_lose)

 

 

5. 고민

• 시뮬레이션으로 구현했지만, DFS로도 구현할 수 있지 않을까?
• 이동횟수를 굳이 저렇게 리스트로 비교하는 방법이 아니라 변수 하나로 할 수 있었을 것같은데...
• nr, nc가 아니라 바로 r, c를 갱신해줘도 됐을 것같다