글 읽기 - bfs 모든 반례통과했지만 틀렸습니다

hsw0194 3년 전 0

뭉쳐있는것이 터질때마다 연쇄가 아니라

터져야 하는것이 한번에 터져야하므로

boom_list에 터져야할 곳들을 넣어두고

boom 함수로 터트리면서 중력적용하게끔 했습니다.

boom 함수는 터지는곳이 맨윗줄이면 '.'으로 바꿔줘야하고 (제 코드에서는 .을 0으로 R을 1로 G를 2로..이런식으로 변환했습니다.)

그렇지 않으면 한칸씩 떨어지게끔 했는데

뭐가 문제인지 잘 모르겠습니다. 반례 다 넣어봤는데 다통과하네요 ㅠㅠㅠ

from sys import stdin
from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
R, C = 12, 6


# target_list는 y는 내림차순,x는 오름차순으로 정렬되어 있음
def boom(target_list, grid):

  # y,x가 터지면 y-1,x가 아래로 내려옴

  while len(target_list) != 0:
    y, x = target_list[0]

    # 맨 꼭대기 층이면 위에서 내려오는게 아니라 0으로 바꿔야함
    if y == 0:
      grid[y][x] = 0

    while y > 0 and grid[y][x] != 0:
      grid[y][x] = grid[y - 1][x]
      y -= 1

    del target_list[0]

  return 0


def bfs(grid, check, q):
  target_list = list()

  while len(q) != 0:
    y, x = q.popleft()
    target_list.append((y, x))

    for k in range(4):
      ny, nx = y + dy[k], x + dx[k]

      if ny == R or nx == C or ny < 0 or nx < 0:
        continue

      # 방문하려는곳이 출발지와 같은 색이고 방문하지 않았다면
      if grid[ny][nx] == grid[y][x] and not check[ny][nx]:
        check[ny][nx] = True
        q.append((ny, nx))

  return sorted(target_list, key=lambda x: (x[0], x[1]))


def traverse(grid, check, chain):
  is_boom = False

  check = [[False] * C for _ in range(R)]
  boom_list = []
  for i in range(R):
    for j in range(C):
      if grid[i][j] != 0 and not check[i][j]:
        check[i][j] = True
        q = deque()
        q.append((i, j))
        target_list = bfs(grid, check, q)

        if len(target_list) >= 4:
          boom_list.append(target_list)
          is_boom = True

  if is_boom:
    return is_boom, chain + 1, boom_list
  else:
    return is_boom, chain, boom_list


def sol():

  grid = []
  for _ in range(R):
    string = stdin.readline().rstrip('\n')
    row = []
    for char in string:
      if char == '.':
        row.append(0)
      elif char == 'R':
        row.append(1)
      elif char == 'G':
        row.append(2)
      elif char == 'B':
        row.append(3)
      elif char == 'P':
        row.append(4)
      elif char == 'Y':
        row.append(5)
    grid.append(row)

  chain = 0

  while True:
    check = [[False] * C for _ in range(R)]
    is_boom, chain, boom_list = traverse(grid, check, chain)

    for PUYO in boom_list:
      boom(PUYO, grid)

    if not is_boom:
      return chain


print(sol())

hsw0194 3년 전 0

RRRRRR

RRRRGG

RRRRRR

RRRRGG

RRRRRR

output : 2로 잘출력되고

RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRBBRR
RRRRRR
RRRRRR
RRRRRR
RRBBRR
RRRRRR
RRRRRR

output:2

......
......
......
......
......
......
......
......
......
......
......
......

output : 0 다 잘됩니당 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

bfs 모든 반례통과했지만 틀렸습니다

hsw0194 3년 전 0

hsw0194 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말