글 읽기 - 반례 부탁드립니다ㅠㅠ

brothersoo 2년 전 0

올려주신 반례 다 확인해본 것 같은데 틀렸다고 나타나네요..
from collections import defaultdict, deque
from sys import stdin
from typing import List, Optional, Tuple


def solution1():

    def _crush(point: list):  # point 미네랄 부순 후 공중에 떠있는 cluster 탐색 후 떨어트리기
        # 포인트! 무조건 위에거부터!
        # 알고보니 문제 조건으로 한번에 두개 이상의 클러스터가 떨어지는 경우는 없다 하여 크게 문제는 없어 보인다..
        # 위에서부터 떨어트린다고 해서 처리되는 문제도 아니였다.. 이건 일단 신경쓰지 않기로!
        dirs: List[tuple] = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        def _fall(clusters: List[list]):  # 공중에 떠있는 cluster 떨어트리기
            def __get_bottoms(cluster: List[list]) -> Optional[List[list]]:  # cluster의 바닥 구하기.
                bottoms: list = []
                bottom_checked: List[bool] = [False for _ in range(C)]
                for mineral in cluster:
                    if not bottom_checked[mineral[1]]:
                        bottoms.append(mineral)
                        bottom_checked[mineral[1]] = True
                return bottoms

            def __get_falling_level(bottoms: List[list]) -> int:  # 클러스터 다음이 바닥이거나 미네랄일때까지의 거리 구하기
                falling_level: int = 1
                reached_bottom: bool = False
                while True:
                    for bottom in bottoms:
                        if bottom[0]-falling_level == 0 or cave[bottom[0]-falling_level-1][bottom[1]] == 'x':
                            reached_bottom = True
                            break  # for break
                    if reached_bottom:
                        break  # while break
                    falling_level += 1
                return falling_level

            for cluster in clusters:
                cluster.sort()  # 바닥 탐색 시, 그리고 떨어트릴 때 아랫쪽 row부터 처리해야 하기 때문에 sort
                bottoms: List[list] = __get_bottoms(cluster)  # 바닥 구하기
                falling_level = __get_falling_level(bottoms)  # 떨어질 거리 구하기
                for mineral in cluster:  # cluster의 모든 미네랄 떨어트리기 falling_level만큼 떨어트리기
                    x, y = mineral
                    cave[x][y] = '.'
                    cave[x-falling_level][y] = 'x'

        def _get_is_floating_dfs(point: int) -> Tuple[bool, Optional[list]]:  # cluster가 공중에 떠있는지 확인. 왠지 dfs로 해야 바닥과 이어져있는지 빠르게 확인할 수 있을 거라고 생각했는데 dfs나 bfs나 차이는 없을 것 같다.
            stack: list = []
            visited = defaultdict(bool)  # !!! visited dict를 각 방향마다 선언해주었다.  !!! 후... 그래도 11%....
            cluster: list = []
            stack.append(point)
            cluster.append(point)  # cluster에 포함된 미네랄들
            visited[tuple(point)] = True
            is_floating: bool = True

            while stack:
                x, y = stack.pop()
                if x == 0:  # cluster에 포함된 미네랄이 바닥위에 있다면 공중에 떠있지 않음
                    is_floating = False
                    break
                if visited[(x, y)] == False:
                    cluster.append([x,y])  # cluster가 공중에 떠있다면 cluster에 포함된 미네랄을 알아야 하기 때문에 저장하기
                visited[(x, y)] = True
                for dir in dirs:
                    dx, dy = dir
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < R and 0 <= ny < C and cave[nx][ny] == 'x' and not visited[(nx, ny)]:
                        stack.append([nx, ny])
            if is_floating:
                return True, cluster
            else:
                return False, None

        cave[point[0]][point[1]] = '.'  # 화살로 인한 미네랄 파괴
        # visited = defaultdict(bool)  # !!!!! 여기가 문제였다 !!!!! 다른 방향에서 시작할지라도 dfs 탐색중 만나는 visited 처리된 미네랄은 같은 cluster 이라 pass 하고자 어쭙잖게 처리하고자 했지만 이러면 floating이 아님에도 floating 처리 될 수가 있다.
        x, y = point
        # 혹시나 해서 추가했지만 문제 조건상 한번에 두개 이상의 클러스터가 떨어지는 경우는 없으므로 하나 떨어질 클러스터 하나씩 처리하면 될 것 같다.
        floating_clusters = []
        for dir in dirs:  # 파괴된 미네랄을 둘러싸고 있던 미네랄들을 시작으로 하여 dfs 탐색.
            dx, dy = dir
            nx, ny = x + dx, y + dy
            if 0 <= nx < R and 0 <= ny < C and cave[nx][ny] == 'x':
                is_floating, cluster = _get_is_floating_dfs([nx, ny])  # cluster가 공중에 떠있는지 확인
                if is_floating:
                    floating_clusters.append(cluster)
        _fall(floating_clusters)  # 공중에 떠있는 cluster들 낙하

    R, C = map(int, stdin.readline().split())
    cave = deque()
    for _ in range(R):
        cave.appendleft(list(stdin.readline())[:C])

    rounds = int(stdin.readline())
    heights = list(map(int, stdin.readline().split()))
    for r in range(rounds):
        height = heights[r] - 1
        if r % 2 == 0:  # 왼쪽 공격
            for i in range(C):
                if cave[height][i] == 'x':
                    _crush([height, i])
                    break
        else: # 오른쪽 공격
            for i in range(C-1, -1, -1):
                if cave[height][i] == 'x':
                    _crush([height, i])
                    break

    for row in reversed(cave):
        print(''.join(row))


if __name__ == "__main__":
    solution1()
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례 부탁드립니다ㅠㅠ

brothersoo 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
