[삼성SW역량][Python/BOJ] 백준 21609 상어 중학교(구현)

 

으렵다!!

그래도 계속 풀다보면 익숙해지겠지 

 

 

이차원 배열을 뒤집어야하는데 

이 문제를 풀면서 포스팅을 작성했다. 

 

참고 : 

https://what-am-i.tistory.com/330?category=1000199 

[python]이차원 배열을 뒤집는 방법_zip(*list)

 

 

 

크기가 가장 큰 블록을 찾을 때

여러 개라면 무지개 블록의 수가 많은 그룹, 무지개 블록의 수도 동일하다면 기준 블록의 행과 열이 가장 큰것을 찾는다. 

(즉, 1. 크기, 2. 무지개 블록의 수, 3. 기준 블록의 행과 열 이 큰 순서)

 

 

무지개 블록을 중복으로 가질 수 있다는 것을 알아야한다. 

 

1. bfs (x,y,color) 

# 블록 그룹 찾기
def bfs(x,y,color) :
    q = deque()
    q.append([x,y])
    
    block_cnt, rainbow_cnt = 1,0
    blocks, rainbows = [[x,y]], []
    
    while q :
        x,y = q.popleft()
        for d in range(4) :
            nx,ny = x +dx[d], y + dy[d]
            # 색이 동일한 일반 블록을 만났을 때 
            if 0<=nx<n and 0<=ny<n and not vis[nx][ny] and mp[nx][ny] == color :
                vis[nx][ny] = 1
                q.append([nx,ny])
                block_cnt +=1 
                blocks.append([nx,ny])
            # 무지개 색의 블록을 만났을 때 
            elif 0<=nx<n and 0<=ny<n and not vis[nx][ny] and mp[nx][ny] == 0 :
                vis[nx][ny] = 1
                q.append([nx,ny])
                block_cnt +=1 
                rainbow_cnt +=1 
                rainbows.append([nx,ny])
                
    # 무지개 블록들은 방문 다시 해제 
    for x,y in rainbows :
        vis[x][y] = 0
    # 총 블록 사이즈, 무지개 블록의 개수, 블록들의 좌표 
    return [block_cnt, rainbow_cnt, blocks+rainbows]

기준 블록의 x,y 좌표와 색이 매개변수로 주어진다. 

덱을 만들어 먼저 기준블록의 좌표를 넣는다. 

 

block과 rainbow block의 개수를 세기위한 변수를 만들고 

각 블락의 위치를 저장할 리스트를 만든다. 

 

BFS를 통해 색이 동일한 일반 블록을 만난 경우, 무지개 색의 블록을 만난 경우로 나누어 vis와 rainbow등 많은 리스트를 채운다. BFS가 끝난 이후 무지개 블록들은 중복하여 가질 수  있으므로 vis를 0으로 설정해준다. 

 

그리고 총 블록의 사이즈, 무지개 블록의 개수, 블록의 좌표를 반환한다. 

블록의 좌표의 첫 좌표는 기준 블록이므로 문제에서 원하는 기준으로 큰 블록그룹을 구할 수  있다. 

(문제에서 원하는 기준은 큰 블록, 무지개 블록 개수, 기준 블록의 행과 열이 큰 순서)

 

 

 

2. Gravity

# 중력 함수 
def gravity(mp) :
	# 아래 행부터 올라오면서  확인한다. 
    for i in range(n-2, -1,-1) :
        for j in range(n) :
        	# 무지개 블록 또는 일반블록이라면 
            if mp[i][j] > -1 :
                r = i 
                while True :
                    if 0<=r+1<n and mp[r+1][j] == -2 : # 아래 칸이 비었을 때 
                        mp[r+1][j] = mp[r][j] # 아래칸으로 값을 넣고 
                        mp[r][j] = -2  # 원래 칸은 빈칸으로 
                        r +=1  # 아래칸으로 위치 변경 
                    else :
                        break

맨 마지막 행 (n-1)번째 행은 내려갈 곳이 없으므로 i는 n-2부터 돈다. 

 

 

 

 

 

 

3. rot90()

# 반시계 회전 
def rot90(mp) :
    mp = list(zip(*mp))[::-1]
    mp = [list(s) for s in mp]
    return mp

포스팅 처음에 뒤집는 포스팅을 링크해뒀다. 

 

 

* 를 통해 unpack한후 zip을 통해 엮고 list를 통해 리스트화 한다.

각각은 튜플형태로 모아져 리스트화 되어있으므로 각각을 리스트화 해준다. 

 

 

 

 

코드 : 

from collections import deque

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

# 블록 그룹 찾기
def bfs(x,y,color) :
    q = deque()
    q.append([x,y])
    
    block_cnt, rainbow_cnt = 1,0
    blocks, rainbows = [[x,y]], []
    
    while q :
        x,y = q.popleft()
        for d in range(4) :
            nx,ny = x +dx[d], y + dy[d]
            # 색이 동일한 일반 블록을 만났을 때 
            if 0<=nx<n and 0<=ny<n and not vis[nx][ny] and mp[nx][ny] == color :
                vis[nx][ny] = 1
                q.append([nx,ny])
                block_cnt +=1 
                blocks.append([nx,ny])
            # 무지개 색의 블록을 만났을 때 
            elif 0<=nx<n and 0<=ny<n and not vis[nx][ny] and mp[nx][ny] == 0 :
                vis[nx][ny] = 1
                q.append([nx,ny])
                block_cnt +=1 
                rainbow_cnt +=1 
                rainbows.append([nx,ny])
                
    # 무지개 블록들은 방문 다시 해제 
    for x,y in rainbows :
        vis[x][y] = 0
    # 총 블록 사이즈, 무지개 블록의 개수, 블록들의 좌표 
    return [block_cnt, rainbow_cnt, blocks+rainbows]

def remove(block) :
    for x,y in block :
        mp[x][y] = -2   

# 중력 함수 
def gravity(mp) :
	# 아래 행부터 올라오면서  확인한다. 
    for i in range(n-2, -1,-1) :
        for j in range(n) :
        	# 무지개 블록 또는 일반블록이라면 
            if mp[i][j] > -1 :
                r = i 
                while True :
                    if 0<=r+1<n and mp[r+1][j] == -2 : # 아래 칸이 비었을 때 
                        mp[r+1][j] = mp[r][j] # 아래칸으로 값을 넣고 
                        mp[r][j] = -2  # 원래 칸은 빈칸으로 
                        r +=1  # 아래칸으로 위치 변경 
                    else :
                    	# while 문 빠져나감
                        break


# 반시계 회전 
def rot90(mp) :
    mp = list(zip(*mp))[::-1]
    mp = [list(s) for s in mp]
    return mp 
    
if __name__=="__main__" :
    
    n,m = map(int,input().split())
    mp = [list(map(int,input().split())) for i in range(n)]
    
    score = 0 
    
    while True :
        # 1. 크기가 가장 큰 블록 찾기
        blocks = []
        vis = [[0]*n for i in range(n)]
        for i in range(n) :
            for j in range(n) :
                # 일반 블록이고 방문한적이 없을 때 
                if mp[i][j] >=1 and vis[i][j] == 0:
                    vis[i][j] = 1
                    block_info = bfs(i,j,mp[i][j]) # 인접한 블록 찾기 # 기준블록  
                    
                    # block_info = [블록크기, 무지개 블록 개수, 블록좌표]
                    if block_info[0] >= 2 :
                        blocks.append(block_info)
                        
        # 블록크기, 무지개 블록 개수,  기준 좌표가 큰 순으로 정렬 
        blocks.sort(reverse = True)
               
        # 블럭 그룹이 없다면 
        if not blocks :
            break 
            
        #2. 블록제거 + 점수 더하기
        remove(blocks[0][2])
        score += blocks[0][0]**2 
        
        #3. 중력 , 4. 90도 회전, 5. 중력
        gravity(mp)
        mp = rot90(mp)
        gravity(mp)
        
    print(score)

 

 

 

참고 블로그 : 

https://jennnn.tistory.com/68

[백준] 21609. 상어 중학교 / python 파이썬