백준 20058: 마법사 상어와 파이어스톰 - 구현, 시뮬레이션 (파이썬, 자바)

마법사 상어와 파이어스톰 성공

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

문제

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다.

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

출력

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

제한

• 2 ≤ N ≤ 6
• 1 ≤ Q ≤ 1,000
• 0 ≤ A[r][c] ≤ 100
• 0 ≤ Li ≤ N

 

 

내 코드

import sys
from collections import deque

#BFS 함수
def bfs(start_x,start_y):
    global tmpSize
    tmpSize+=1 #사이즈 ++;

    que=deque()
    que.append([start_x,start_y])

    visited[start_x][start_y]=True

    while que:
        x,y=que.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            if nx<0 or nx>=s or ny<0 or ny>=s:
                continue

            if arr[nx][ny]>0 and not visited[nx][ny]:
                visited[nx][ny]=True
                que.append([nx,ny])
                tmpSize+=1 #사이즈 ++;


#영역별 회전 함수
def rotate(x,y,l):
    global arr

    #newArr에 가져온 배열의 수들이 (0,0)부터 세팅되도록 할 것임
    newArr=[]
    cnt=0 #요소들이 몇개인지 기억
    for i in range(x,x+l):
        newArr.append([])
        for j in range(y,y+l):
            newArr[cnt].append(arr[i][j])
        cnt+=1

    #회전한 상태의 수들을 순서대로 rotatedNum에 넣을 것임.
    rotatedArrNum=[]
    for i in range(len(newArr)):
        for j in range(len(newArr[i])):
            rotatedArrNum.append(newArr[l-1-j][i])
    
    #rotatedNum에 있는 수들을 다시 순서대로 원본에 넣으면 된다.
    cnt=0
    for i in range(x,x+l):
        for j in range(y,y+l):
            arr[i][j]=rotatedArrNum[cnt]
            cnt+=1


#녹이는 함수
def isNear():
    meltList=[] #녹는 위치들을 저장할 것임
    for i in range(s):
        for j in range(s):
            cnt=0 #주위에 인접한 얼음들을 카운트 할 것임
            for k in range(4):
                nx=i+dx[k]
                ny=j+dy[k]

                if nx<0 or nx>=s or ny<0 or ny>=s:
                    continue

                if arr[nx][ny]>0:
                    cnt+=1
            
            if cnt<3: #지금 위치와 인접한 얼음 수가 3개 이상이 아니고,
                if arr[i][j]>0: #지금 위치에 얼음이 1 이상이면, (얼음은 음수가 될 수 없어서 체크해야함)
                    meltList.append([i,j]) #녹일 리스트에 추가.

    #리스트에 넣은 놈들을 녹인다
    for x,y in meltList:
        arr[x][y]-=1



#메인 코드 부분
n,q=map(int,sys.stdin.readline().split())

s=2**n #전체 가로, 세로 길이를 s라 할 것임

dx=[-1,0,1,0]
dy=[0,1,0,-1]

arr=[]
for _ in range(s):
    arr.append(list(map(int,sys.stdin.readline().split())))

command=list(map(int,sys.stdin.readline().split()))


#Step 1: 회전+녹이기
for i in range(q):
    length=2**(command[i])

    if length==1: #나누었을 때 각 배열 크기가 1이면 회전해도 변화 X
        isNear() #바로 얼음이 주는지 수행.
        continue

    #(0,0)부터 원하는 크기의 영역만큼씩 탐색
    for j in range(0,s,length):
        for k in range(0,s,length):
            rotate(j,k,length)

    isNear() #모든 영역들에 대해 회전이 끝나면 얼음 녹기



#Step 2: 회전과 녹이기 모두 끝나면 덩어리들을 체크해야 한다
visited=[[False]*s for _ in range(s)]

maxSize=[]
for i in range(s):
    for j in range(s):
        if arr[i][j]>0 and not visited[i][j]:
            tmpSize=0 #덩어리별로 사이즈를 저장해서,
            bfs(i,j)
            maxSize.append(tmpSize) #리스트에 넣는다.


answer1=0
answer2=0

for x in arr:
    answer1+=sum(x)

if maxSize: #빈 리스트가 아니면 최대값이 답. 아니면 0
    answer2=max(maxSize)

print(answer1)
print(answer2)

풀이 및 접근)

- 이 문제는 구현+시뮬레이션 문제이다. 문제에서 시키는대로 잘 수행하면 된다. 신경 써야할 부분은 배열 회전에 관한 것이다. 배열을 시계 방향으로 90도 회전하는 공식은 arr[i][j] = arr[n-1-j][i] 이다. 원래 있던 곳의 값이,

    x좌표 = 배열길이 - 1 - 이전y 좌표

    y좌표 = 이전 x좌표

에 있는 값이 된다.

- 위 공식을 대입하기 위해서는, 배열의 초기 좌표가 (0,0)일 때 성립한다. 따라서 배열을 회전하기 전에, 초기 좌표를 (0,0)으로 세팅하는 작업이 필요했다. 세팅 후 회전한 배열의 요소들을 순서대로 새로운 배열에 저장한 후, 이를 원본 배열에 다시 순서대로 대입하면 원본이 회전한 배열로 거듭나는 것이다.

- 나머지는 구현 + BFS or DFS를 통해 해결한다.

- 필자는 처음에 DFS를 통해 탐색을 했는데 이 때 파이썬 특성상 sys.setrecursionlimit(10**8) 등과 같은 재귀 제한을 늘리지 않으면 통과가 되지 않았다. 파이썬은 간혹 DFS시에 이런 설정을 해주어야 한다 (틀린 것이 아님)

- 이것이 약간 찜찜하여 BFS로 다시 구현하니 당연히 통과가 되었다.

   

 

자바 ver.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[][] arr;
    static int[] dx={-1,0,1,0};
    static int[] dy={0,1,0,-1};
    static String[] input;
    static int s;
    static int[] command;
    static int tmpSize;

    static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine().split(" ");
        int n=Integer.parseInt(input[0]);
        int q=Integer.parseInt(input[1]);

        s=(int)Math.pow(2,n);

        arr=new int[s][s];

        for(int i=0; i<s; i++){
            input = br.readLine().split(" ");
            for(int j=0; j<s; j++){
                arr[i][j]=Integer.parseInt(input[j]);
            }
        }


        command=new int[q];
        input = br.readLine().split(" ");
        for(int i=0; i<q; i++){
            command[i]=Integer.parseInt(input[i]);
        }
        
        for(int i=0; i<q; i++){
            int length=(int)Math.pow(2,command[i]);

            if(length==1){
                isNear();
                continue;
            }

            for(int j=0; j<s; j+=length){
                for(int k=0; k<s; k+=length){
                    rotate(j,k,length);
                }
            }

            isNear();
        }

        visited=new boolean[s][s];

        for(int i=0; i<s; i++){
            Arrays.fill(visited[i],false);
        }

        List<Integer> maxSize=new ArrayList<>();

        for(int i=0; i<s; i++){
            for(int j=0; j<s; j++){
                if(arr[i][j]>0 && !visited[i][j]){
                    tmpSize=0;
                    bfs(i,j);
                    maxSize.add(tmpSize);
                }
            }
        }

        int answer1=0;
        int answer2=0;

        for(int i=0; i<s; i++){
            answer1+=Arrays.stream(arr[i]).sum();
        }

        if(!maxSize.isEmpty()){
            answer2= Collections.max(maxSize);
        }

        System.out.println(answer1);
        System.out.println(answer2);
    }
    
    private static void isNear() {
        List<int[]> meltList=new ArrayList<>();

        for(int i=0; i<s; i++){
            for(int j=0; j<s; j++){
                int cnt=0;
                for(int k=0; k<4; k++){
                    int nx=i+dx[k];
                    int ny=j+dy[k];

                    if(nx<0 || nx>=s || ny<0 || ny>=s){
                        continue;
                    }

                    if(arr[nx][ny]>0){
                        cnt++;
                    }
                }
                if(cnt<3){
                    if(arr[i][j]>0){
                        meltList.add(new int[]{i,j});
                    }
                }
            }
        }

        for(int i=0; i<meltList.size(); i++){
            arr[meltList.get(i)[0]][meltList.get(i)[1]]-=1;
        }
    }

    
    private static void rotate(int x,int y, int l) {
        
        int[][] newArr=new int[l][l];
        int tmpX=0;

        for(int i=x; i<x+l; i++){
            int tmpY=0;
            for(int j=y; j<y+l; j++){
                newArr[tmpX][tmpY++]=arr[i][j];
            }
            tmpX++;
        }
        
        int[] rotatedNum=new int[l*l];
        int cnt=0;
        for(int i=0; i<l; i++){
            for(int j=0; j<l; j++){
                rotatedNum[cnt]=newArr[l-1-j][i];
                cnt++;
            }
        }

        cnt=0;
        for(int i=x; i<x+l; i++){
            for(int j=y; j<y+l; j++){
                arr[i][j]=rotatedNum[cnt];
                cnt++;
            }
        }
    }

    private static void bfs(int start_x, int start_y){
        tmpSize++;

        List<int[]> que=new ArrayList<>();
        que.add(new int[] {start_x,start_y});
        visited[start_x][start_y]=true;

        while(!que.isEmpty()){
            int[] ints = que.get(0);
            que.remove(0);
            int x=ints[0];
            int y=ints[1];
            for(int i=0; i<4; i++){
                int nx=x+dx[i];
                int ny=y+dy[i];

                if(nx<0 || nx>=s || ny<0 || ny>=s){
                    continue;
                }

                if(arr[nx][ny]>0 && !visited[nx][ny]){
                    visited[nx][ny]=true;
                    que.add(new int[] {nx,ny});
                    tmpSize++;
                }
                
            }
        }
    }
}