[백준] 21609(파이썬) 상어 중학교

21609번 상어 중학교

BFS+시뮬레이션 문제이다.
이 문제의 경우 2021 삼성 상반기 오전 공채 SW 역량테스트 문제 (SW A형)이다.
풀이에 대해 숙지 하고 있자.

문제를 정리해보겠다.

• 블럭은 검은색(-1), 무지개(0), 일반(1~m) 색상이 있다.
• 일반 블럭은 m가지 색상이 있고, m이하의 자연수로 표현한다.
• 블럭 그룹은 연결된 블럭의 집합이다.
  • 블럭 그룹 내에는 일반 블럭이 하나이상 있어야하고, 그룹내 일반 블럭의 색은 모두 동일하다.
  • 검은색 블럭은 포함하면 안되고, 무지개 블럭은 상관 없다.
  • 그룹의 블럭개수는 2이상 이어야 하며, 블럭 그룹은 서로 이동가능한 인접한 칸으로 이루어져있다.
  • 블럭 그룹의 기준 블럭은 무지개 블럭이 아닌 블럭중 행의 번호가 작은, 열의 번호가 작은 블럭이다.

• 오토 플레이 기능

1. 크기가 가장 큰 블럭 그룹, 무지개 블럭의 수가 가장 큰 블럭 그룹, 기준 블럭의 행이 가장 큰것, 기준 블럭의 열이 가장 큰것 순으로 블럭 그룹 하나를 찾는다.
2. 1에서 찾은 블럭 그룹의 모든 블럭을 제거하고, 블럭 그룹의 블럭 수의 제곱 만큼 점수를 획득한다.(b**2)
3. 격자에 중력이 작용한다.
4. 격자가 반시게 방향으로 90도 회전한다.
5. 다시 격자에 중력이 작용한다.

여기까지 문제의 풀이이다.

이번 문제는 사실 엄청 어려운 구현은 아니다. 로테이션, 중력은 구현 난이도가 그리 높지 않기 때문이다.
이번 문제는 블럭 그룹의 선정과 블럭을 지우는 과정이 중요하다고 생각한다.

시나리오

1. 오토 플레이 모드 -> while 1로 루프를 돌게함.(단, 찾은 블럭그룹이 존재하지 않을경우 break)

2. 2중 for 문을 이용하여, 격자를 다 탐색해서, (크기가 가장 큰 블럭 그룹, 무지개 블럭의 수가 가장 큰 블럭 그룹, 기준 블럭의 행이 가장 큰것, 기준 블럭의 열이 가장 큰것 순)에 해당하는 블럭 그룹을 찾는다.
   - 그럼 bfs 탐색에서 반환값으로 블럭의 크기, 무지개 블럭의 크기, 기준 블럭 좌표(x,y), 그룹의 블럭 좌표들 이 필요하다.
   - 무지개 블럭은 이후 탐색에서 중복으로 사용될 수 있기 때문에 탐색이 끝나기 전에 방문처리를 초기화 해줘야 한다.
   
   위와 같이 3행 1,2,3 열 처럼 중복으로 사용이 가능하다.

3. 블럭을 제거한다.(-2를 빈칸으로 설정), 점수를 계산한다.

4. 중력작용

5. 회전

6. 중력작용

이처럼 시나리오를 작성하고 코드를 짜보면,

• 오토 플레이 코드

#오토 플레이
while 1:
    visited=[[0 for _ in range(n)] for _ in range(n)] #방문 체크
    block_group=[] #블럭 그룹
    count=0 #인접한 블럭 수

    # bfs 탐색할때, i,j 가 기준블럭이 된다.(기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.)
    for i in range(n):
        for j in range(n):
            #방문하지 않았고, 일반 블록일 경우(무지개 블록이 시작하는 경우를 제외) ->  무지개 블럭 부터 탐색할 경우 bfs 에서 같은 색의 블럭을 찾을때 무지개 블럭만 찾게됨.
            if visited[i][j]==0 and graph[i][j]>0:
                res=bfs(i,j,graph[i][j]) # res= (총 갯수, 무지개 갯수, 해당 블럭들의 좌표)
                
                # res 가 None 이 아니고, 전체 블럭의 수가 count 보다 크고 2보다 크거나 같은 경우만 필터링한다.
                if res and count<=res[0] and res[0]>=2:
                    block_group.append(res)
                    count=res[0]
    
    #bfs 탐색을 했는데, 가능한 블럭 그룹이 없으면 종료.
    if len(block_group)==0:
        print(score)
        exit()
    
    # 내림차순으로 정렬
    ans=sorted(block_group, key=lambda x : (-x[0], -x[1], -x[2],-x[3]))
    #정렬 결과중 맨 앞의 것이 조건에 부합하는 블럭 그룹
    ans=ans[0]
    score+=count**2

    # 좌표 빈칸 처리 (빈칸을 -2로 처리)
    for x,y in ans[4]:
        graph[x][y]=-2

    #중력작용
    gravity()

    #90도 반시계 회전
    graph=turn()
    
    #다시 중력
    gravity()

모든 블럭을 탐색하면서, 가장 큰 블럭그룹의 후보들을 block_group 리스트에 담고, 이를 정렬을 통해서 가장 큰 블럭그룹을 얻어온다.
탐색의 조건을 보면 시작은 일반 블럭일 경우, 방문하지 않은 경우에 탐색을 시작한다.
점수처리를 하고, 빈칸 처리를 하고, 중력, 회전, 중력을 작용하면 된다.

• 가장 큰 블럭 그룹 탐색

#가장큰 블록그룹 찾기
def bfs(x,y,color):
    q=deque()
    q.append([x,y])
    visited[x][y]=1

    #기준 블럭
    standard_block_x=x
    standard_block_y=y

    total_cnt, rainbow =1,0 #전체 블록수, 무지개 블럭 수
    normal, rainbow_lst = [[x,y]],[] #일반 블럭, 무지개 블럭 좌표 리스트

    while q:
        x,y=q.popleft()
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            if 0<=nx<n and 0<=ny<n:
                # 아직 방문하지 않았고, 일반블럭일때
                if visited[nx][ny]==0 and graph[nx][ny]==color:
                    q.append([nx,ny])
                    visited[nx][ny]=1
                    normal.append([nx,ny])
                    total_cnt+=1
                # 아직 빙문하지 않았고, 무지개 블럭일때
                if visited[nx][ny]==0 and graph[nx][ny]==0:
                    q.append([nx,ny])
                    visited[nx][ny]=1
                    rainbow_lst.append([nx,ny])
                    total_cnt+=1
                    rainbow+=1
    
    # 무지개의 방문처리는 초기화(이후 탐색에서 중복으로 사용될 수 있음.)
    for x,y in rainbow_lst:
        visited[x][y]=0

    return total_cnt, rainbow, standard_block_x, standard_block_y, normal+rainbow_lst # 총 갯수, 무지개 갯수, 기준블럭, 해당 블럭들의 좌표

일반 블럭과 무지개 블럭을 나눠서 처리한다.

• 중력 작용

# 아랫 방향으로 어디까지 갈 수 있는지 탐색
def gravity_bfs(x,y):
    q=deque()
    q.append([x,y])

    while q:
        x,y=q.popleft()
        nx=x+1
        #범위내에 다음이 빈칸이면,
        if 0<=nx<n and graph[nx][y]==-2:
            q.append([nx,y])
    #갈수있는 제일 아래의 x,y를 반환
    return x,y

#중력작용(검은색 블록 제외 아래로 이동)
def gravity():
    for i in range(n-2,-1,-1): #밑의 한줄 위부터 체크한다.(맨 밑줄은 내려갈 곳이 없음.)
        for j in range(n):
            #블럭이 일반 혹은 무지개 블럭이면
            if graph[i][j]>=0 :
                x,y=gravity_bfs(i,j)
                graph[x][y]=graph[i][j] #이동
                #만약 처음좌표와 탐색결과의 좌표가 같지 않다면,
                if (x,y)!=(i,j):
                    #처음 자리는 빈칸으로 변경
                    graph[i][j]=-2

가장 밑의 바로 위에 줄부터 시작하면 된다.
해당 열의 아래방향으로 탐색을 하면서, 갈수 있는 가장 밑을 찾는다.

• 회전

#회전
def turn():
    turn_graph=[[0 for _ in range(n)] for _ in range(n)] #기존 좌표는 건들면 안된다.
    for i in range(n):
        for j in range(n):
            turn_graph[n-j-1][i]=graph[i][j]
    return turn_graph

회전의 규칙을 적용해서 좌표를 바꿔주면 된다.
기존 그래프는 그대로 둔 상태로 새로운 그래프를 이용한다.

전체 코드

#가장큰 블록그룹 찾기
def bfs(x,y,color):
    q=deque()
    q.append([x,y])
    visited[x][y]=1

    #기준 블럭
    standard_block_x=x
    standard_block_y=y

    total_cnt, rainbow =1,0 #전체 블록수, 무지개 블럭 수
    normal, rainbow_lst = [[x,y]],[] #일반 블럭, 무지개 블럭 좌표 리스트

    while q:
        x,y=q.popleft()
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            if 0<=nx<n and 0<=ny<n:
                # 아직 방문하지 않았고, 일반블럭일때
                if visited[nx][ny]==0 and graph[nx][ny]==color:
                    q.append([nx,ny])
                    visited[nx][ny]=1
                    normal.append([nx,ny])
                    total_cnt+=1
                # 아직 빙문하지 않았고, 무지개 블럭일때
                if visited[nx][ny]==0 and graph[nx][ny]==0:
                    q.append([nx,ny])
                    visited[nx][ny]=1
                    rainbow_lst.append([nx,ny])
                    total_cnt+=1
                    rainbow+=1
    
    # 무지개의 방문처리는 초기화(이후 탐색에서 중복으로 사용될 수 있음.)
    for x,y in rainbow_lst:
        visited[x][y]=0

    return total_cnt, rainbow, standard_block_x, standard_block_y, normal+rainbow_lst # 총 갯수, 무지개 갯수, 기준블럭, 해당 블럭들의 좌표

# 아랫 방향으로 어디까지 갈 수 있는지 탐색
def gravity_bfs(x,y):
    q=deque()
    q.append([x,y])

    while q:
        x,y=q.popleft()
        nx=x+1
        #범위내에 다음이 빈칸이면,
        if 0<=nx<n and graph[nx][y]==-2:
            q.append([nx,y])
    #갈수있는 제일 아래의 x,y를 반환
    return x,y

#중력작용(검은색 블록 제외 아래로 이동)
def gravity():
    for i in range(n-2,-1,-1): #밑의 한줄 위부터 체크한다.(맨 밑줄은 내려갈 곳이 없음.)
        for j in range(n):
            #블럭이 일반 혹은 무지개 블럭이면
            if graph[i][j]>=0 :
                x,y=gravity_bfs(i,j)
                graph[x][y]=graph[i][j] #이동
                #만약 처음좌표와 탐색결과의 좌표가 같지 않다면,
                if (x,y)!=(i,j):
                    #처음 자리는 빈칸으로 변경
                    graph[i][j]=-2

#회전
def turn():
    turn_graph=[[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            turn_graph[n-j-1][i]=graph[i][j]
    return turn_graph


import sys
input=sys.stdin.readline
from collections import deque

n,m = map(int, input().split()) #n: 격자 크기, m: 색상 개수
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))

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

#점수
score=0

#오토 플레이
while 1:
    visited=[[0 for _ in range(n)] for _ in range(n)] #방문 체크
    block_group=[] #블럭 그룹
    count=0 #인접한 블럭 수

    # bfs 탐색할때, i,j 가 기준블럭이 된다.(기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.)
    for i in range(n):
        for j in range(n):
            #방문하지 않았고, 일반 블록일 경우(무지개 블록이 시작하는 경우를 제외) ->  무지개 블럭 부터 탐색할 경우 bfs 에서 같은 색의 블럭을 찾을때 무지개 블럭만 찾게됨.
            if visited[i][j]==0 and graph[i][j]>0:
                res=bfs(i,j,graph[i][j]) # res= (총 갯수, 무지개 갯수, 해당 블럭들의 좌표)
                
                # res 가 None 이 아니고, 전체 블럭의 수가 count 보다 크고 2보다 크거나 같은 경우만 필터링한다.
                if res and count<=res[0] and res[0]>=2:
                    block_group.append(res)
                    count=res[0]
    
    #bfs 탐색을 했는데, 가능한 블럭 그룹이 없으면 종료.
    if len(block_group)==0:
        print(score)
        exit()
    
    # 내림차순으로 정렬
    ans=sorted(block_group, key=lambda x : (-x[0], -x[1], -x[2],-x[3]))
    #정렬 결과중 맨 앞의 것이 조건에 부합하는 블럭 그룹
    ans=ans[0]
    score+=count**2

    # 좌표 빈칸 처리 (빈칸을 -2로 처리)
    for x,y in ans[4]:
        graph[x][y]=-2

    #중력작용
    gravity()

    #90도 반시계 회전
    graph=turn()
    
    #다시 중력
    gravity()

역시 삼성 기출이다. 이번 문제는 비교적 오래걸리기는 했어도, 난이도 자체는 그리 높지 않았던것 같았다. 단 무지개 블럭은 공유될 수 있다는 점을 간과했기 때문에 좀 많이 헤맸다. ㅋㅋㅋㅋ

좀더 화이팅 해서 문제를 풀어보자!