[백준_21610]마법사 상어와 비바라기 with Python

백준(BOJ) 삼성 SW 역량 테스트 기출 문제 문제집: 마법사 상어와 바바라기(골드 5)

문제 출처: https://www.acmicpc.net/problem/21610

21610번: 마법사 상어와 비바라기

 

1. 알고리즘

시간초과 문제를 제외하곤 작동 알고리즘 자체는 단순했음

문제에서 설명하는 대로만 작성하면 성공

• 이동 횟수(M)만큼 반복
• 구름을 이동시켜줌
• 이동한 구름 위치의 바구니에 물을 1씩 추가하고, 구름의 위치를 저장
• 이동한 구름 위치에서 4개의 대각선 방향을 탐색하여 물이 있는 바구니의 갯수만큼 현재 위치에 물 추가
  • 대각선 방향 탐색 시, 범위 밖의 좌표는 이어져 있지 않은 것을 본다
• 전체 칸을 탐색하여 물이 2 이상인 칸에 구름 생성
  • 위에서 이동한 구름 위치와 동일한 위치에는 물이 2 이상이더라도 생성 X
• M번 반복 이후, 물 양의 합 출력

 

 

2. 유의 사항

• 구름 이동 시에는 0번과 N-1번 인덱스가 연결되어 있지만, 물 버그 복사를 위해 대각선 탐색 시에는 범위 밖의 대각선 좌표는 연결X

 

 

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

• 시간 초과
  • 구름 이동할 좌표 탐색 시, while 문으로 범위 안에 들어올 때까지 값을 더하고 빼주도록 함(시간초과의 원인1)
    • N을 더해, 음의 수가 나오는 경우를 처리하고, N나머지 연산을 통해 N보다 큰 값이 나오는 경우를 처리.

    • #시간 초과 코드
      """
      next_cloud_x = cloud_x + (dx[d-1]*s)
      next_cloud_y = cloud_y + (dy[d-1]*s)
      
          while not 0<=next_cloud_x<N or not 0<=next_cloud_y<N:
                  
              if not 0<=next_cloud_x<N:
                  if next_cloud_x < 0:
                      next_cloud_x += N
                  else:
                      next_cloud_x -= N
      
              if not 0<=next_cloud_y<N:
                  if next_cloud_y < 0:
                      next_cloud_y += N
                  else:
                      next_cloud_y -= N
      """
      
      #해결 코드
      next_cloud_x = (N + cloud_x + (dx[d-1]*s)) % N
      next_cloud_y = (N + cloud_y + (dy[d-1]*s)) % N

  • 새 구름 생성 시, 구름이 있던 리스트를 탐색하여 이전 구름의 위치를 검사함(시간초과의 원인2)
    • 구름의 위치에 따라 물을 추가할 때, N*N행렬을 만들어 구름의 위치를 표시하여 해당 인덱스만 검사하도록 함.

    • #시간 초과 코드
      #if (i, j) not in move_clouds:
      
      #해결 코드
      if not is_cloud[i][j]:
          clouds.append((i, j))
          A[i][j] -= 2

 

 

4. 소스코드

상세 코드 설명은 주석 참고

import sys
 
input_func = sys.stdin.readline
if __name__ == '__main__':
    N, M = map(int, input_func().split())
    A = [list(map(int, input_func().split())) for _ in range(N)]
    
    #초기 구름 위치 설정
    clouds = [(N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1)]
    
    #좌표 이동 설정
    dx = [0, -1, -1, -1, 0, 1, 1, 1]
    dy = [-1, -1, 0, 1, 1, 1, 0, -1]
    for _ in range(M):      #M번 반복
        d, s = map(int, input_func().split())
        
        #구름 이동
        move_clouds = []
        for cloud_idx in range(len(clouds)):
            cloud_x, cloud_y = clouds[cloud_idx]
            #N을 더해 음의 좌표 처리, N나머지 연산으로 N보다 큰 좌표 처리
            next_cloud_x = (N + cloud_x + (dx[d-1]*s)) % N
            next_cloud_y = (N + cloud_y + (dy[d-1]*s)) % N
            
            move_clouds.append((next_cloud_x, next_cloud_y))    #구름이 이동한 좌표를 리스트에 추가
        
        #구름의 위치를 확인해주기 위한 N*N 행렬
        is_cloud = [[False]*N for _ in range(N)]
        #구름의 위치에 따라 물 추가, 구름 위치 표기
        for mv_x, mv_y in move_clouds:
            A[mv_x][mv_y] += 1
            is_cloud[mv_x][mv_y] = True
        
        #대각선 위치를 탐색해주기 위한 좌표 이동 인덱스 설정
        find_directions = [1, 3, 5, 7]
        #구름의 대각선 위치를 검사하여 물 복사 버그
        for mv_x, mv_y in move_clouds:
            is_rain_count = 0
            #대각선 칸에 물이 있는 칸이 몇 개 인지 세기
            for fd in find_directions:
                find_x, find_y = mv_x+dx[fd], mv_y+dy[fd]
                
                #범위 밖인 경우 제외
                if not 0<=find_x<N or not 0<=find_y<N:
                    continue
                #물이 없는 경우 제외
                if A[find_x][find_y] == 0:
                    continue
 
                is_rain_count += 1
            
            #물이 있는 만큼 물 추가
            A[mv_x][mv_y] += is_rain_count
        
        #새 구름 생성
        clouds = []
        for i in range(N):
            for j in range(N):
                #물 양이 1이하이면 제외
                if A[i][j] <= 1:
                    continue
                
                #위에서 이동한 구름 위치가 아닌 경우, 구름 생성 및 물 양-2
                if not is_cloud[i][j]:
                    clouds.append((i, j))
                    A[i][j] -= 2
    
    #2차원 행렬 > 1차원 행렬 > sum 전체 합 계산, 출력
    print(sum(sum(A, [])))

 

5. 고민