글 읽기 - (파이썬) 혹시 반례좀 찾아주실 수 있으실까요??

cd2420 2년 전 0

테스트 케이스와, 질문에 올라와 있는 반례로 테스트 해보고 정답이 나오는 걸 확인했는데,

8퍼센트에서 자꾸 틀렸다고 뜹니다.... 반례를 못찾겠습니다 ㅠㅜㅠ 도와주실 수 있으실까요??

from collections import deque

MINERAL_ICON = 'x'

# 부숴지는 미네랄 좌표
def findBreakPoint(height, direction):
    tmp_row = graph[r - height][:]
    if direction == 'L':
        for i in range(c):
            if tmp_row[i] == MINERAL_ICON:
                return (r - height, i)
    else:
        for i in range(c-1, -1, -1):
            if tmp_row[i] == MINERAL_ICON:
                return (r - height, i)

# 부숴진후 클러스터 좌표 반환
def findCluster(x, y, visited):
    
    q = deque([(x, y)])
    clusters = []
    while q:
        x, y = q.popleft()
        for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx  < r and 0 <= ny < c and graph[nx][ny] == MINERAL_ICON and not visited[nx][ny] :
                visited[nx][ny] = True
                clusters.append((nx, ny))
                q.append((nx, ny))
    return clusters

r, c = map(int, input().split())
graph = [list(input()) for _ in range(r)]
n = int(input())
heights = list(map(int, input().split()))
for i in range(n):
    
    # 왼쪽
    direction = 'L'
    if i % 2 != 0:
        #오른쪽
        direction = 'R'
    h = heights[i]
    breakPoint = findBreakPoint(h, direction)


    if breakPoint:
        x, y = breakPoint
        graph[x][y] = '.'
        visited = [[False] * c for _ in range(r)]

        # 미네랄 부숴진 후 위치 조정이 필요한 클러스터 담을 리스트.
        change_cluster = []
        for gx in range(r):
            for gy in range(c):
                if not visited[gx][gy] and graph[gx][gy] == MINERAL_ICON:
                    cluster = findCluster(gx, gy, visited)

                    # 공중에 떠 있는 클러스터 찾기
                    if cluster and max(cluster)[0] != r - 1:
                        cluster.sort(reverse=True)
                        change_cluster.append(cluster)

        for change in change_cluster:

            for cx, cy in change:
                graph[cx][cy] = '.'

            # 공중에 떠 있는 클러스터를 옮기기 위한 거리
            change_num = r - 1 - change[0][0]
            for cx, cy in change:
                for check_i in range(cx + 1, r):
                    if graph[check_i][cy] == 'x' and check_i - cx - 1 < change_num:
                        change_num = check_i - cx - 1

            for cx, cy in change:
                graph[cx + change_num][cy] = 'x'
for gr in graph:
    print(''.join(gr))

iiiiiiiiiiiiiiiiii 1년 전 0

혹시 반례 찾으셨나요ㅠㅠ 게시판에 올라와있는 반례는 다 통과했는데 저도 계속 8%에서 틀렸습니다가 뜹니다...

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

문제

문제

출처

ICPC

(파이썬) 혹시 반례좀 찾아주실 수 있으실까요??

cd2420 2년 전 0

iiiiiiiiiiiiiiiiii 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말