글 읽기 - 반례를 알 수 있을까요

srlee96 3년 전 0

안녕하세요,

2933번 문제풀이를 하고 있는데

반례를 찾지 못하고 있습니다.

혹시 도움을 주실 수 있는분 있을까요

from collections import deque


def crash(h, side):
    # 왼쪽에서 들어온 경우 (L) , 오른쪽에서 들어온 경우 (R) 나누어서 미네랄 삭제
    x, y = (N-h), 0 if side == 'L' else M-1
    if side == 'L':
        while arr[x][y] == 0:
            y+=1
            if y>=M: return -1, -1
    else:
        while arr[x][y] == 0:
            y-=1
            if y<0: return -1, -1
    arr[x][y] = 0
    return x, y

def bfs(i, j):
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    visited = [[0 for _ in range(M)] for _ in range(N)]
    visited[i][j] = 1
    que = deque()
    s = set()
    que.append((i, j))
    s.add((i, j))
    flag = False
    # 탐색하는 클러스터가 바닥에 닿아있으면 (x==N-1) flag True 공중에 떠있다면 클러스터 집합 s 를 반환
    while que:
        x, y = que.popleft()
        if x == N-1:
            flag = True
            return flag, None
        for d in range(4):
            nx, ny = x+dx[d], y+dy[d]
            if 0<=nx<N and 0<=ny<M and visited[nx][ny] == 0 and arr[nx][ny] == 1:
                visited[nx][ny] = 1
                que.append((nx, ny))
                s.add((nx, ny))
    return flag, s

def move_down(s):
    dist = float('inf')
    # 비교를 위해 클러스터를 지움
    for i, j in s:
        arr[i][j] = 0
    # 클러스터가 이동할수 있는 거리 계산
    for x, y in s:
        i, j = x, y
        while i<N and arr[i][j] == 0:
            i+=1
        dist = min(dist, i-x-1)
    # 클러스터 이동
    for i, j in s :
        if i + dist < N:
            arr[i+dist][j] = 1


#11:25
if __name__ == '__main__':
    #sys.setrecursionlimit(10**6)
    sys.stdin = open("input.txt", 'r')
    N, M = map(int, input().split())
    arr = []
    for i in range(N):
        temp = list(map(int, input().replace('.', '0').replace('x', '1')))
        arr.append(temp)
    T = int(input())
    # 0 : left 1: right
    heights = list(map(int, input().split()))
    for h in range(len(heights)):
        # 홀수 짝수로 나누어 왼쪽 오른쪽 방향 선택
        if h%2 == 0:
            x, y = crash(heights[h], 'L')
        else:
            x, y = crash(heights[h], 'R')
        # check clusters status
        if x!=-1 and y!=-1:
            if arr[x - 1][y] == 1:
                f, cluster = bfs(x - 1, y)
                if cluster:
                    # move minerals
                    move_down(cluster)
                    continue

            if y - 1 >= 0 and arr[x][y - 1] == 1:
                f, cluster = bfs(x, y - 1)
                if cluster:
                    # move minerals
                    move_down(cluster)
                    continue

            if y + 1 < M and arr[x][y + 1] == 1:
                f, cluster = bfs(x, y + 1)
                if cluster:
                    # move minerals
                    move_down(cluster)
                    continue


    for i in range(N):
        for j in range(M):
            print(str(arr[i][j]).replace('0', '.').replace('1','x'), end='')
        print()

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

문제

문제

출처

ICPC

반례를 알 수 있을까요

srlee96 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말