글 읽기 - 질문게시판에서 찾은 반례가 이해가 안됩니다.

rlarudgh2017 1년 전 0

......
......
......
......
......
....Y.
....Y.
....Y.
....RR
...YRR
..GGYY
..GGYY

답은 2

터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

본문에 이렇게 적혀있는데 답이 4가 되어야 하는거 아닌가요?? 아래는 제 코드입니다

from collections import deque

dy = [0, 0, -1, 1]
dx = [-1, 1, 0, 0]
board = [['.'] * 6 for _ in range(12)]
for i in range(12):
    tmp = input()
    for j in range(6):
        board[i][j] = tmp[j]

def inRange(y, x):
    if 0 <= y < 12 and 0 <= x < 6:
        return True
    return False

def bfs(start_y, start_x, color, visited):
    q = deque([(start_y, start_x)])
    visited[start_y][start_x] = True
    cnt = 0
    while q:
        y, x = q.popleft()
        cnt += 1
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if not inRange(ny, nx) or board[ny][nx] != color or visited[ny][nx]:
                continue
            q.append((ny, nx))
            visited[ny][nx] = True
    return cnt

def explode(start_y, start_x, color):
    q = deque([(start_y, start_x)])
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if not inRange(ny, nx) or board[ny][nx] != color:
                continue
            q.append((ny, nx))
            board[ny][nx] = '.'

def traversal():
    cnt = 0
    visited = [[False] * 6 for _ in range(12)]
    for i in range(12):
        for j in range(6):
            if board[i][j] == '.':
                continue
            elif bfs(i, j, board[i][j], visited) >= 4:
                cnt += 1
                explode(i, j, board[i][j])
    return cnt

def gravity():
    for j in range(6):
        pos = 11
        for i in range(11, -1, -1):
            if board[i][j] == '.':
                pos = i
                break
        else:
            continue
        tmp = pos
        for i in range(pos, -1, -1):
            if board[i][j] != '.':
                board[tmp][j] = board[i][j]
                board[i][j] = '.'
                tmp -= 1

ans = 0
tmp = traversal()
while tmp > 0:
    ans += tmp
    gravity()
    tmp = traversal()

print(ans)

repelit 1년 전 1

......
......
......
......
......
....Y.
....Y.
....Y.
....RR
...YRR
..GGYY
..GGYY

1연쇄 뒤

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

......

....Y.

....Y.
....Y.
....Y.

이렇게 해서 2연쇄입니다.

즉, 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.라는 뜻은

한번에 여러개의 뿌요가 터지더라도 그룹마다가 아닌, 시간에 따라 연쇄가 한번 추가된다는 뜻입니다.

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

문제

문제

출처

ICPC

질문게시판에서 찾은 반례가 이해가 안됩니다.

rlarudgh2017 1년 전 0

repelit 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말