[백준_20058]마법사 상어와 파이어스톰 with Python

 

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

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

20058번: 마법사 상어와 파이어스톰

1. 알고리즘

• 마법사 상어의 단계 L에 따라 나뉠 부분 격자의 크기, 한 줄에 나뉘는 부분 격자의 개수 연산.
• 나뉠 부분의 시작 인덱스 리스트 연산.(0부터 부분 격자의 갯수까지 반복, 숫자*부분 격자 크기)
• 부분 격자의 크기만큼 행을 나누고, 부분 격자의 크기만큼 열을 나누어 회전 수행, 기존 그래프 업데이트.
  • 위에서 구한 인덱스 리스트를 사용, [시작 인덱스:시작 인덱스 + 부분 격자 크기]로 행을 나눔.
  • 위에서 구한 인덱스 리스트를 사용, [시작 인덱스:시작 인덱스 + 부분 격자 크기]로 열을 나눔.
  • 회전은 zip 함수 사용.
  • 회전한 각 부분 격자를 new_row리스트에 행 별로 열 요소 추가.
  • 부분 격자 크기만큼 나뉜 행의 회전 연산이 끝나면 ice_field 행 값 갱신.
• 브루트 포스로 모든 칸에 대해 인접한 칸의 얼음 양을 확인, 조건에 따라 값을 갱신.
  • 각 인접 칸을 확인하며 얼음이 있는 칸의 개수를 연산.
  • 조건에 따라 값을 갱신해줘야 하는 칸의 (행 번호, 열 번호)를 change_field 리스트에 추가.
  • 모든 칸에 대한 인접 칸 얼음 양 확인이 끝나면, change_field 리스트의 요소에 따라 ice_field의 해당 칸 값 갱신.
• 모든 칸에 대하여 최대 얼음 덩어리의 크기를 BFS로 확인.
  • 방문 여부를 확인해주기 위한 visited 리스트로, 반복문 내부에서 공유하여 동일한 칸을 연산하지 않도록 함.
  • 얼음 덩어리 탐색을 위한 BFS 함수 내부에서 얼음 덩어리의 크기를 반환.
  • max_ice_section변수에 최댓값 갱신.
• 위에서 확인한 최대 얼음 덩어리의 크기를 출력.
• ice_field 리스트를 1차원 리스트로 바꾸고, 전체 값을 더하여 total_ice 값 연산, 출력.

 

2. 유의 사항

• L 연산은 단계를 의미하는 것으로, 순차적인 연산을 필요로 하지 않음.
  • L = 2 가 주어졌을 때, 1단계를 수행하고 2단계를 수행해야 하는 것이 아님.
• 인접 칸 얼음 양에 따른 현재 칸 얼음 변화는 동시에 일어남.

 

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

 

 

4. 소스코드

상세 코드 설명은 주석

import sys
from collections import deque
 
#BFS, 얼음 덩어리 찾는 함수
def find_ice_section(start, graph):
    route = deque([start])
    visited[start[0]][start[1]] = 1
    count_ice_section = 1
 
    while route:
        x, y = route.popleft()
 
        for idx in range(4):
            nx, ny = x + d[idx][0], y + d[idx][1]
 
            if 0 <= nx < field_len and 0 <= ny < field_len:
                if graph[nx][ny] != 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    route.append((nx, ny))
                    count_ice_section += 1
 
    return count_ice_section
 
 
if __name__=="__main__":
    N, Q = map(int, sys.stdin.readline().split())
    ice_field = [list(map(int, sys.stdin.readline().split())) for _ in range(2**N)]
    L = list(map(int, sys.stdin.readline().split()))
 
    field_len = 2**N
    #마법사 상어가 수행한 단계만큼 반복
    for l in L:
        section_len = 2**l
        section_line = (field_len)//section_len
        
        #부분 격자 회전
        #부분 격자 시작 인덱스 리스트
        separate_idx = [i*section_len for i in range(0, section_line)]
        #시작 인덱스에 따라 행 분리
        for section_row in separate_idx:
            row_temp = ice_field[section_row:section_row+section_len]
            new_row = [[] for i in range(0, len(row_temp))]
            #시작 인덱스에 따라 분리한 행의 열 분리, 회전 > 부분 격자
            for section_column in separate_idx:
                section_temp = [rt[section_column:section_column+section_len] for rt in row_temp]
                section_temp = list(map(list, zip(*section_temp[::-1])))
                #new_row 각 행에 열 요소 추가
                for str in range(len(section_temp)):
                    new_row[str].extend(section_temp[str])
            #행 단위 연산 후 ice_field 행 갱신
            ice_field[section_row:section_row+section_len] = new_row
        
        d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        change_field = []
        #모든 칸에 대해 인접 칸의 얼음 양 확인
        for r in range(0, field_len):
            for c in range(0, field_len):
                if ice_field[r][c] == 0:
                    continue
 
                count_ice = 0
                for idx in range(4):
                    nr, nc = r+d[idx][0], c+d[idx][1]
                    if 0 <= nr < field_len and 0 <= nc < field_len:
                        if ice_field[nr][nc] != 0:
                            count_ice += 1
 
                #조건에 따라 값 변경이 필요한 칸 좌표(r, c) 리스트 추가
                if count_ice < 3:
                    change_field.append((r, c))
 
        #인접 칸 얼음 양에 따른 값 변경
        for r, c in change_field:
            ice_field[r][c] -= 1
 
 
    #얼음 덩어리 크기 확인
    visited = [[0]*field_len for _ in range(field_len)]
    max_ice_secion = 0
    for r in range(field_len):
        for c in range(field_len):
            if ice_field[r][c] == 0 or visited[r][c] != 0:
                continue
 
            ice_section_size = find_ice_section((r, c), ice_field)
            max_ice_secion = max(max_ice_secion, ice_section_size)
 
    #남은 얼음 총합
    total_ice = sum(sum(ice_field, []))
 
    print(total_ice)
    print(max_ice_secion)

 

 

5. 고민

• Python으로 통과하려면 시간을 어떻게 줄일 수 있을까
• 얼음 덩어리 크기 확인할 때 얼음 총합을 구해줬으면 시간이 좀 덜 걸렸을까
• 부분 격자를 회전할 때, 다른 방법이 있을 것 같은데...