leah

my dev_log

0%

BOJ 11559

Posted on In ,

문제 조건

1. bfs()

  • 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 한꺼번에 없어질 것, 1연쇄에 해당
  • 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터지고, 여러 그룹이더라도 1연쇄에 해당

2. check_fall()

  • 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어질 것

3. while

  • 뿌요가 없어지고 난 후 bfs부터 다시 반복

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
from collections import deque
import sys

input = sys.stdin.readline
dir = [[-1,0],[1,0],[0,-1],[0,1]]

# string to string(char) array
board = [list(map(str, input().strip())) for _ in range(12)]

# 뿌요 터뜨리기
def bfs(dx, dy, flag):
  q = deque()
  c = [[0]*6 for _ in range(12)]
  q.append([dx, dy])
  cnt = 1
  c[dx][dy] = cnt

  # 한 점씩 상하좌우 체크
  # 같은 색의 뿌요 체크
  while q:
    dx, dy = q.popleft()

    for i in range(4):
      x = dx + dir[i][0]
      y = dy + dir[i][1]

      if 0 <= x < 12 and 0 <= y < 6:
        if board[x][y] == board[dx][dy] and c[x][y] == 0:
          cnt += 1
          c[x][y] = 1
          q.append([x, y])

  # 연쇄되는 경우
  if cnt >= 4:
    flag += 1
    for i in range(12):
      for j in range(6):
        # pop 시키기
        if c[i][j] == 1:
          board[i][j] = "."

  return flag

def check_fall():
  # 마지막 줄 제외하고 역순으로 체크 (아래로 떨어지므로)
  for i in range(10, -1, -1):
    for j in range(6):
      # 아래로 떨어져야 하는 경우
      if board[i][j] != "." and board[i+1][j] == ".":
        for k in range(i+1, 12):
          # 뿌요가 없는 & 가장 밑으로 현재의 뿌요를 떨어트려야 함
          # break point
          if k == 11 and board[k][j] == ".":
            board[k][j] = board[i][j]
          # k < 11인데 뿌요가 있는 경우
          elif board[k][j] != ".":
            board[k-1][j] = board[i][j]
            break
        
        board[i][j] = "."

answer = 0

# case 반복
while True:
  # 이 때 cnt는 0인지 아닌지만 체크하는 변수로,
  # 다른 색의 뿌요 그룹이 터져도 동시에 터지는 것으로 간주하여 한번의 연쇄로 취급함
  cnt = 0

  # 한 board 케이스 연쇄되는 경우의 수 체크
  for i in range(12):
    for j in range(6):
      if board[i][j] != ".":
        cnt += bfs(i, j, cnt)

  # break point: board 전체 검사 했는데 cnt == 0
  if cnt == 0:
    print(answer)
    break

  # 연쇄된 경우 -> 다시 처음부터 board 체크해야 함
  else:
    answer += 1
  
  check_fall()

Python

  • string to string(char) array

    1
    [list(map(str, input().strip())) for _ in range(12)]