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

문제 설명

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다.

일반적인 BFS/ DFS 문제보다 신경써서 구현해야 할 부분들이 훨씬 까다로운 문제이므로

과정을 하나하나 잘 살펴보면서 구현하시는 것을 추천드립니다.

---

풀이 과정

먼저 두 방법으로 풀면서 코드를 두 가지로 작성해보았습니다.

코드①은 구현해야 할 부분들을 그대로 나열식으로 작성한 코드이며 길이가 좀 더 깁니다.

코드②는 코드①을 좀더 깔끔하고, 중복되는 코드들을 줄여 정리한 코드입니다.

두 코드 모두 접근 방식은 같습니다.

---

먼저 공통되는 부분인 rotate(회전)함수와 gravity(중력)함수부터 설명드리자면,

rotate는 반시계(왼쪽)방향으로 90도 회전을 해야 하기 때문에

(0, 0) 좌표는 => (n-1, 0) 좌표로 이동을 하게 되고

(0, 1) 좌표는 => (n-2, 0) 좌표로 이동을 하게 됩니다.

이런식으로 직접 행렬을 그려서 비교해보면

(x, y) 좌표는 => (n-1-y, x) 좌표로 이동함을 알 수 있습니다.

 

gravity는 벽(-1)이나 경계를 만날 때 까지 아래 빈칸으로 계속 쭉 떨어지게 됩니다.

그래서 밑의 행부터 시작하여 차례대로 while문을 통해 내려갈 수 있는 곳 까지 내려가게 해줍니다.

 

이제 핵심이 되는 BFS 코드(find_group함수)입니다.

풀이①은 문제에서 조건1에 해당하는

크기가 가장 큰 블록 그룹을 찾는다. 
그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 
그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 
그 것도 여러개이면 열이 가장 큰 것을 찾는다.

이 부분을 함수 안에 같이 구현을 하였습니다.

while문을 통해 그룹을 지은 다음, 그룹의 크기가 2보다 작으면 그룹을 만들지 않고 return 합니다.

현재 만든 그룹과 최대 그룹을 비교를 해서

현재 만든 그룹이 더 크면 최대 그룹을 바꿔줍니다.

크기가 같다면, 무지개 블록의 수가 많은 블록을 최대 그룹으로 하고

그것마저 같다면 기준행, 열을 비교하여 선정을 하면 됩니다.

 

이 방법을 모두 find_group 함수 안에 순서대로 작성하였습니다.

코드①

from collections import deque

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

for i in range(n):
    graph.append(list(map(int, input().split())))


def find_group(a, b):
    visited = [[False] * n for _ in range(n)]
    groupQ = []
    if graph[a][b] == -1 or graph[a][b] == -2:
        return
    if graph[a][b] > 0:
        myColor = graph[a][b]
    else:
        myColor = 0
    cnt = 1
    queue = deque()
    queue.append((a, b))
    visited[a][b] = True
    while queue:
        x, y = queue.popleft()
        groupQ.append((x, y))

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny]:
                continue
            if graph[nx][ny] == -1 or graph[nx][ny] == -2:
                continue
            if graph[nx][ny] > 0:
                if myColor == 0:
                    myColor = graph[nx][ny]
                elif myColor != graph[nx][ny]:
                    continue
            cnt += 1
            queue.append((nx, ny))
            visited[nx][ny] = True

    if cnt < 2:
        return

    global groupCnt, maxQ

    if cnt > groupCnt:
        groupCnt = cnt
        maxQ = groupQ
    elif cnt == groupCnt:
        thisZeroCnt, maxZeroCnt = 0, 0
        for i in range(cnt):
            if graph[groupQ[i][0]][groupQ[i][1]] == 0:
                thisZeroCnt += 1
        for i in range(groupCnt):
            if graph[maxQ[i][0]][maxQ[i][1]] == 0:
                maxZeroCnt += 1
        if thisZeroCnt == maxZeroCnt:
            groupQ.sort(key=lambda x: x[1])
            groupQ.sort(key=lambda x: x[0])
            maxQ.sort(key=lambda x: x[1])
            maxQ.sort(key=lambda x: x[0])
            gx, gy, mx, my = 0, 0, 0, 0
            for i in range(cnt):
                if graph[groupQ[i][0]][groupQ[i][1]] != 0:
                    gx = groupQ[i][0]
                    gy = groupQ[i][1]
                    break
            for i in range(groupCnt):
                if graph[maxQ[i][0]][maxQ[i][1]] != 0:
                    mx = maxQ[i][0]
                    my = maxQ[i][1]
                    break

            if gx > mx:
                maxQ = groupQ
            elif gx == mx:
                if gy > my:
                    maxQ = groupQ

        elif thisZeroCnt > maxZeroCnt:
            maxQ = groupQ

    return


def gravity():
    for i in range(n-2, -1, -1):
        for j in range(n):
            if graph[i][j] != -1:
                tmp = i
                while tmp + 1 < n and graph[tmp+1][j] == -2:
                    graph[tmp+1][j] = graph[tmp][j]
                    graph[tmp][j] = -2
                    tmp += 1


def rotate():
    newGraph = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            newGraph[n - 1 - j][i] = graph[i][j]
    return newGraph


answer = 0

while True:
    groupCnt = 0
    maxQ = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] > 0:
                find_group(i, j)
    if not maxQ:
        break
    answer += len(maxQ)**2
    for x, y in maxQ:
        graph[x][y] = -2
    gravity()
    graph = rotate()
    gravity()
print(answer)

---

코드 1과 다른 부분은 BFS 코드(find_group함수)입니다.

코드②은 find_group함수에서는 일단 그룹을 형성하여 그 그룹의 크기와 0(무지개)크기, 일반블록+무지개블록의 좌표를 담은 리스트를 반환을 해주었고

 

이 리스트들을 하나의 큐에 넣은 후에

정렬을 통해 최대 큐(조건에 맞는 큐)를 선정하였습니다.

 

또한, visited를 함수 안이 아닌 바깥에 선언을 함으로써, 중복으로 형성하는 그룹을 없앴고

대신, 0칸(무지개)은 다음턴에 다른 그룹들과도 형성될 수 있으므로

다시 미방문 처리를 해주어야 합니다.

 

코드②

from collections import deque

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

for i in range(n):
    graph.append(list(map(int, input().split())))

def find_group(a, b, color):
    queue = deque()
    queue.append([a, b])

    block_cnt, zero_cnt = 1, 0
    blocks = [[a, b]]
    zeros = []

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

            if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny]:
                continue

            if graph[nx][ny] == color:
                visited[nx][ny] = True
                queue.append([nx, ny])
                block_cnt += 1
                blocks.append([nx, ny])

            elif graph[nx][ny] == 0:
                visited[nx][ny] = True
                queue.append([nx, ny])
                block_cnt += 1
                zeros.append([nx, ny])
                zero_cnt += 1

    for x, y in zeros:
        visited[x][y] = False

    return [block_cnt, zero_cnt, blocks + zeros]

def gravity():
    for i in range(n-2, -1, -1):
        for j in range(n):
            if graph[i][j] != -1:
                tmp = i
                while tmp + 1 < n and graph[tmp+1][j] == -2:
                    graph[tmp+1][j] = graph[tmp][j]
                    graph[tmp][j] = -2
                    tmp += 1

def rotate():
    newGraph = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            newGraph[n - 1 - j][i] = graph[i][j]
    return newGraph

answer = 0

while True:
    visited = [[False]*n for _ in range(n)]
    maxQ = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] > 0 and not visited[i][j]:
                visited[i][j] = True
                block = find_group(i, j, graph[i][j])
                if block[0] >= 2:
                    maxQ.append(block)
    print(maxQ)
    maxQ.sort(reverse=True)

    if not maxQ:
        break
    answer += maxQ[0][0]**2
    for x, y in maxQ[0][2]:
        graph[x][y] = -2
    gravity()
    graph = rotate()
    gravity()
    print(graph)
print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !