[BOJ] 16768 - Mooyo Mooyo

사용 언어: Python3

문제

백준 16768

문제를 요약하자면,
K개 이상의 같은 수가 붙어있을 때 그 수들은 동시에 사라진다.
더이상 사리질게 없을 때까지 사라진 뒤, 맨 마지막에 남은 보드판을 출력하는 문제이다.

이 문제를 해결하기 위해 필요한 기초 지식은 아래와 같다.

• Flood Fill 이론
• Flood Fill 이후 처리
• 2차원 배열에서 내부 요소들을 이동시키는 방법

또한 구현해야할 함수는 아래와 같다.

• BFS 혹은 DFS로 그룹을 찾고, 그룹 개수를 반환하는 함수
• 그룹의 요소 수가 K 이상일 때, 해당 요소들을 삭제하는 함수
• 보드판의 요소들을 아래로 내려오게 하는 함수

내 풀이

첫 번째

import sys
sys.setrecursionlimit(10000)

dx, dy = [0,-1,0,1], [1,0,-1,0]
def dfs(x,y):
  global K, board, group, ck
  tmp = [(x,y)]
  if ck[x][y]:
    return
  for i in range(4):
    xx, yy = x+dx[i], y+dy[i]
    if not ck[xx][yy] and board[x][y] != 0 and board[x][y] == board[xx][yy]: # 테두리 0 추가 안하면 여기서 인덱스 에러
      tmp.append((xx,yy))
      ck[xx][yy] = True # 방문 체크
  if len(tmp) >= K:
    group.extend(tmp)

N, K = map(int, input().split())

# 테두리 0 추가
board = [[int(x) for x in '0'+input()+'0'] for _ in range(N)]
board.insert(0, [0 for _ in range(12)])
board.insert(N+1, [0 for _ in range(12)])

group = [] # blood fill 그룹
ck = [[False for _ in range(12)] for _ in range(N+2)] # 방문했는지

# blood fill 그룹 찾기
for i in range(1,N):
  for j in range(1,11):
    dfs(i,j)


print(group)
print(len(group))

# output
# for row in board:
#   print(''.join(row))

두 번째 - 0405 추가

pullDown() 함수만 혼자서 만들어봤다.

r = 6
M = [list(input()) for _ in range(r)]

def pullDown():
  # 세로로 탐색
  for i in range(10):
    tmp = [] # 0 아닌것들 담기
    for j in range(r):
      if M[j][i] != '0':
        tmp.append(M[j][i])

    for k in range(r-len(tmp)):
      M[k][i] = '0'
    for k in range(r-len(tmp), r):
      M[k][i] = tmp[k-(r-len(tmp))]

pullDown()

print()
for row in M:
  print(''.join(row))

입출력

다른 사람 풀이

DFS 이용

def new_array(N):
  return [[False for _ in range(10)] for _ in range(N)]
  
N, K = map(int, input().split())
board = [list(input()) for _ in range(N)]
ck = new_array(N) # 방문했는지
ck2 = new_array(N) # 지워도 되는지

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

def dfs(x,y):
  # 몇 개의 수가 한 그룹에 있는가
  ck[x][y] = True # 방문
  cnt = 1 # 기본적으로 나 하나
  for i in range(4):
    xx,yy = x+dx[i],y+dy[i]
    if xx<0 or xx>=N or yy<0 or yy>=10:
      continue
    if ck[xx][yy] or board[x][y] != board[xx][yy]:
      continue
    cnt += dfs(xx,yy)
  return cnt
    
def dfs2(x,y,val):
  ck2[x][y] = True # ck2: 지워도 되는지 체크
  # 지우는 연산
  board[x][y] = '0' # 0으로 바꾸기
  for i in range(4):
    xx,yy = x+dx[i],y+dy[i]
    if xx<0 or xx>=N or yy<0 or yy>=10:
      continue
    if ck2[xx][yy] or board[xx][yy] != val: # ck2!!!
      continue
    dfs2(xx,yy,val)

def pullDown():
  # 세로줄부터 확인
  for i in range(10):
    tmp = [] # 0이 아닌 것들 모아둘 곳
    for j in range(N):
      if board[j][i] != '0':
        tmp.append(board[j][i])
    # 윗줄부터 0으로 채우고
    for k in range(N-len(tmp)):
      board[k][i] = '0'
    # 순서대로 아랫줄 채우기
    for k in range(N-len(tmp), N):
      board[k][i] = tmp[k-(N-len(tmp))]

while True:
  isExist = False # 바뀌는게 있는 동안 계속 반복
  ck = new_array(N)
  ck2 = new_array(N)
  for i in range(N):
    for j in range(10):
      if board[i][j] == '0' or ck[i][j]:
        continue
      res = dfs(i,j) # flood fill 그룹의 원소수 세기
      # print(res,board[i][j])
      if res >= K:
        dfs2(i, j, board[i][j]) # 요소 삭제하기
        isExist = True
      
  if not isExist:
    break
  pullDown() # 아래로 밀기

# output
for row in board:
  print(''.join(row))
    

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기