[BOJ] 21609 상어 중학교

삼성기출문제집에서 본 기억이 있었습니다. 그리고 그 중 제가 풀어본 것들과 비슷하게 하루종일 구현하고 나면 한번에 끝나는 법이 없고 수정하는데도 한참 걸렸습니다...

중력, 회전, 조건에 맞는 bfs와 리턴되는 값 이것들만 잘 설계하면 풀릴 문제라고 생각했습니다.

일단 중력부터 구현해주었습니다. 밑에서부터 올라오다 조건에 맞는 값을 찾으면 다른 블럭이 있거나 -1 또는 맨밑일때 까지 그 값의 위치를 내려주었습니다.

def gravity():
    for i in range(n-1,-1,-1):
        for j in range(n):
            if board[i][j]>=0:
                start=i
                while True:
                    if 0<=start+1<n:
                        if board[start+1][j]==-2:
                            board[start+1][j]=board[start][j]
                            board[start][j]=-2
                            start+=1
                        else:
                            break
                    else:
                        break

그 다음으로 구현한것은 회전입니다.

def rotate():
    global board
    rotated_board=[[0 for i in range(n)]for j in range(n)]
    for i in range(n):
        for j in range(n):
            rotated_board[n-j-1][i]=board[i][j]
    board=rotated_board

가장 애먹은 부분인 BFS 입니다.

x,y,색깔을 받아주고 bfs를 진행하며 얻은 위치값을 색깔이 같거나 무지개블록인 경우 큐에 넣어주었습니다. 이 때 각 경우에 맞는 큐를 따로 생성해주었습니다.

색깔이 같은 블럭의 위치를 담은 큐는 기준 블럭끼리의 비교, 무지개 블럭의 위치를 담은 큐는 방문했던 무지개 블럭을 다시 방문하지 않은 상태로 돌려주기 위해 필요했습니다.

또한 무지개 블럭의 개수와 모든 방문한 블럭의 값을 저장해줄 변수도 따로 만들어주었습니다. 이렇게 일반블럭과 무지개 블럭의 방문에 대해 넣어주어야 할 값이 너무 달라서 그냥 if elif를 써주었습니다.

모든 상어문제들이 이런지는 몰라도 변수도 너무 많아서 고생했습니다. 특히 기준 블럭끼리의 비교를 하기 위해서는 위치값들을 오름차순 정렬을 해 주어야 하지만 최대 넓이를 구할 때는 내림차순 정렬을 해주어야 한다는 것을 문제를 세심히 읽지 않아서 허무할 정도로 한참 해맸습니다.

def bfs(X,Y,color):
    global board,visited
    queue=deque([[X,Y]])
    size=1
    locate=[[Y,X]]
    cnt_rainbow=0
    locate_rainbow=[]
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if board[ny][nx]==color and visited[ny][nx]==0:
                    visited[ny][nx]=1
                    locate.append([ny,nx])
                    size+=1
                    queue.append([nx,ny])
                elif board[ny][nx]==0 and visited[ny][nx]==0:
                    visited[ny][nx]=1
                    locate_rainbow.append([ny,nx])
                    cnt_rainbow+=1
                    size+=1
                    queue.append([nx,ny])

    for y,x in locate_rainbow:
        visited[y][x]=0
    if size>1:
        return (size,cnt_rainbow,sorted(locate),locate_rainbow)
    return False

 

마지막으로 매번 방문을 초기화하고 각 함수들을 사용할 메인? 부분을 만들어주었습니다.

매번 n*n의 방문을 확인할 배열을 초기화시켜주고, bfs를 진행한 값을 a라는 변수에 넣어준 뒤 a가 False가 아니라면 scoreboard에 넣어주었습니다. scoreboard안에 들어있는 값들은 (크기,무지개 블록 수, 오름차순 정렬된 방문한 색이 같은 블록의 위치값(y,x), 방문한 무지개 블록의 위치값) 이렇게 되어있습니다. 이중 for 문을 통과하여 탐색을 끝내면, scoreboard안의 값들을 내림차순 정렬해주고, 맨 앞의 값을 사용했습니다. 위치값들이 들어있는 두 배열을 합치면 그것이 크기만큼의 배열이고 방문한 모든 블록입니다. 따라서 그 배열 안에 있는 원소들을 이용해 board안의 사용된 위치들을 -2로 초기화해주었습니다. 그리고 gravity -> rotate -> gravity, 이것들을 이중 for문을 끝낸 뒤 scoreboard가 비어있을 때 까지 반복해주었습니다.

totalscore=0

while True:
    scoreboard=[]
    visited=[[0 for i in range(n)]for j in range(n)]
    for i in range(n):
        for j in range(n):
            if 0<board[i][j] and visited[i][j]==0:
                visited[i][j]=1
                a=bfs(j,i,board[i][j])
                if a:
                    scoreboard.append(a)

    if not scoreboard:
        print(totalscore)
        break
    #print(scoreboard)
    mx_size,mx_rainbow,block_used,rainbow_block_used=sorted(scoreboard,reverse=True)[0]
    totalscore+=mx_size**2
    for y,x in block_used+rainbow_block_used:
        board[y][x]=-2
    
     gravity()
     rotate()
     gravity()

깔끔하게 해본 총 코드입니다.

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

n,m=map(int,input().split())
dx=[0,0,1,-1]
dy=[1,-1,0,0]

board=[list(map(int,input().split())) for i in range(n)]

def bfs(X,Y,color):
    global board,visited
    queue=deque([[X,Y]])
    size=1
    locate=[[Y,X]]
    cnt_rainbow=0
    locate_rainbow=[]
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if board[ny][nx]==color and visited[ny][nx]==0:
                    visited[ny][nx]=1
                    locate.append([ny,nx])
                    size+=1
                    queue.append([nx,ny])
                elif board[ny][nx]==0 and visited[ny][nx]==0:
                    visited[ny][nx]=1
                    locate_rainbow.append([ny,nx])
                    cnt_rainbow+=1
                    size+=1
                    queue.append([nx,ny])

    for y,x in locate_rainbow:
        visited[y][x]=0
        
    if size>1:
        return (size,cnt_rainbow,sorted(locate),locate_rainbow)
    return False
                    

def gravity():
    for i in range(n-1,-1,-1):
        for j in range(n):
            if board[i][j]>=0:
                start=i
                while True:
                    if 0<=start+1<n:
                        if board[start+1][j]==-2:
                            board[start+1][j]=board[start][j]
                            board[start][j]=-2
                            start+=1
                        else:
                            break
                    else:
                        break

def rotate():
    global board
    rotated_board=[[0 for i in range(n)]for j in range(n)]
    for i in range(n):
        for j in range(n):
            rotated_board[n-j-1][i]=board[i][j]
    board=rotated_board

totalscore=0

while True:
    scoreboard=[]
    visited=[[0 for i in range(n)]for j in range(n)]
    for i in range(n):
        for j in range(n):
            if 0<board[i][j] and visited[i][j]==0:
                visited[i][j]=1
                a=bfs(j,i,board[i][j])
                if a:
                    scoreboard.append(a)

    if not scoreboard:
        print(totalscore)
        break
        
    mx_size,mx_rainbow,block_used,rainbow_block_used=sorted(scoreboard,reverse=True)[0]
    totalscore+=mx_size**2
    
    for y,x in block_used+rainbow_block_used:
        board[y][x]=-2
        
    gravity()
    rotate()
    gravity()

이런 유형은 한번에 성공 못하면 급격하게 피곤해지는 것 같습니다..

 

# bfs를 통해 얻어내야 할 값 (크기,무지개 블록 수,
# 행이 가장 작은 = 가장 왼쪽 그리고 열의 번호가 가 작은, (x,y)순으로 sort 하면 될 것
# 

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

n,m=map(int,input().split())
dx=[0,0,1,-1]
dy=[1,-1,0,0]

board=[list(map(int,input().split())) for i in range(n)]

def bfs(X,Y,color):
    global board,visited
    queue=deque([[X,Y]])
    size=1
    locate=[[Y,X]]
    cnt_rainbow=0
    locate_rainbow=[]
    #print('실행됨')
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<n:
                if board[ny][nx]==color and visited[ny][nx]==0:
                    visited[ny][nx]=1
                    locate.append([ny,nx])
                    size+=1
                    queue.append([nx,ny])
                elif board[ny][nx]==0 and visited[ny][nx]==0:
                    #print(ny,nx)
                    visited[ny][nx]=1
                    locate_rainbow.append([ny,nx])
                    cnt_rainbow+=1
                    size+=1
                    queue.append([nx,ny])

    for y,x in locate_rainbow:
        visited[y][x]=0
    #print(size)
    #print(cnt_rainbow,'무지개')
    ''',cnt_rainbow,sorted(located))'''
    if size>1:
        return (size,cnt_rainbow,sorted(locate),locate_rainbow)
    return False
                    
'''
def gravity(): # 중력 구현
    for i in range(n):
        for j in range(1,n):
            if board[~j][i]!='-1' and board[~j][i]!=None and board[~j+1][i]==None:
                try:
                    while j>=0 and board[~j+1][i] == None:
                        board[~j][i],board[~j+1][i]=board[~j+1][i],board[~j][i]
                        j-=1
                except:
                    pass
'''
def gravity():
    for i in range(n-1,-1,-1):
        for j in range(n):
            if board[i][j]>=0:
                start=i
                while True:
                    if 0<=start+1<n:
                        if board[start+1][j]==-2:
                            board[start+1][j]=board[start][j]
                            board[start][j]=-2
                            start+=1
                        else:
                            break
                    else:
                        break

def showboard():
    for i in range(n):
        for j in range(n):
            print(board[i][j]if board[i][j]!=-2 else 'X',end='\t'if j!=n-1 else '\n')

def rotate(): # 회전 구현
    global board
    rotated_board=[[0 for i in range(n)]for j in range(n)]
    for i in range(n):
        for j in range(n):
            rotated_board[n-j-1][i]=board[i][j]
    board=rotated_board
'''
showboard()
gravity()
print()
showboard()
board=rotate()
print()
showboard()
gravity()
print()
showboard()
'''
t=1
totalscore=0

while True:
    scoreboard=[]
    visited=[[0 for i in range(n)]for j in range(n)]
    for i in range(n):
        for j in range(n):
            if 0<board[i][j] and visited[i][j]==0:
                visited[i][j]=1
                a=bfs(j,i,board[i][j])
                if a:
                    scoreboard.append(a)

    if not scoreboard:
        print(totalscore)
        break
    #print(scoreboard)
    mx_size,mx_rainbow,block_used,rainbow_block_used=sorted(scoreboard,reverse=True)[0]
    totalscore+=mx_size**2
    for y,x in block_used+rainbow_block_used:
        board[y][x]=-2
    
    if True:
        #print(t,end='\n\n')
        #showboard()
        gravity()
        #print('g')
        #showboard()
        rotate()
        #print('r')
        #showboard()
        gravity()
        #print('g')
        #showboard()
        #print()
        #print()
        #t+=1
    
    '''
    gravity()
    rotate()
    gravity()
'''
'''
test case
5 3
2 2 -1 3 -1
None None 2 0 -1
None None None 1 2
-1 None 1 3 2
None None 2 2 1
'''