문제 설명
https://www.acmicpc.net/problem/21609
21609번: 상어 중학교
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록
www.acmicpc.net
문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다.
일반적인 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)전체 문제 & 코드는 위의 깃에 정리되어 있습니다.
팔로우 & 맞팔은 환영입니다 !
'Algorithm > DFS & BFS' 카테고리의 다른 글
| [백준] 14502 연구소 (Python 파이썬) (1) | 2021.10.17 |
|---|---|
| [백준] 12100 2048 (Easy) (Python 파이썬) (0) | 2021.10.14 |
| [백준] 13460 구슬 탈출2 (Python 파이썬) (0) | 2021.10.14 |
| [프로그래머스] 거리두기 확인하기 (Python 파이썬) (0) | 2021.10.09 |
| [백준] 14888 연산자 끼워넣기 (Python 파이썬) (0) | 2021.10.08 |