글 읽기 - 11퍼 틀린 이유 남기고 갑니다

appie701 3년 전 0

저같은 경우는 클러스터 떨어뜨리는 걸 구현하는 함수에서 (down함수에서 53-59)

공중에 떠있는 클러스터의 바닥리스트(바로 밑에 미네랄이 없는 좌표의 집합)가 예를들어서

[(x1,y1), (x2,y2)]라고 하겠습니다.

그럼 이걸 순회하면서 일단 x1,y1 부터 시작해서 위로 한칸씩 올려보면서 클러스터에 속하면 아래로 이동시켜줬는데요,

이렇게 할 경우 바닥리스트에 속한 좌표중 항상 더 아래에 있는 좌표먼저 이동시키지 않는다는 문제가 있습니다.

그렇게 하면 뭐가 문제냐면, 예를들어 바닥리스트에 다음과같은 두 좌표가 있다고 해보겠습니다 [(4,2),(2,2).....]

각각 4행2열과 2행2열을 의미하구요, 클러스터는 2만큼 떨어진다고 했을 때, 만약 (2,2)를 먼저 떨어뜨리면?

추후에 (4,2)를 떨어뜨리면서 (4,2)자리는 "."이 되기 때문에 (2,2)에서 (4,2)로 떨어진 미네랄은 표현을 못하게 됩니다.

이거때매 너무 오랜시간을 뺏겨서 혹시 같은걸로 고민하시는 분 계실까 남기고갑니다..

from collections import deque


def bfs(r,c):
    l = []
    visited = [[False]*m for _ in range(n)]
    q = deque()
    q.append((r,c))
    visited[r][c] = True
    while q:
        x,y = q.popleft()
        if x == n-1:
            return
        if cave[x+1][y] == 0:  # 바닥 리스트
            l.append((x,y))

        if x!=0:
            if cave[x-1][y] and not visited[x-1][y]:  # 상
                visited[x-1][y] = True
                q.append((x-1,y))
        if x!=n-1:
            if cave[x+1][y] and not visited[x+1][y]:  # 하
                visited[x+1][y] = True
                q.append((x+1, y))
        if y!=0:
            if cave[x][y-1] and not visited[x][y-1]:  # 좌
                visited[x][y-1] = True
                q.append((x,y-1))
        if y!=m-1:
            if cave[x][y+1] and not visited[x][y+1]:  # 우
                visited[x][y+1] = True
                q.append((x,y+1))

    down(l, visited)


def down(rclist, checklist):
    global cave

    mind = n+1
    for x,y in rclist:
        dis = 0
        while True:
            dis += 1
            if x+dis == n-1:
                break
            if cave[x+dis+1][y] == 1 and not checklist[x+dis+1][y]:
                break

        if dis < mind:
            mind = dis

    for x,y in rclist: #rclist는 바닥리스트
        while cave[x][y] == 1 and checklist[x][y]:
            cave[x][y] = 0
            cave[x + mind][y] = 1
            x = x - 1
            if x == -1:
                break


n, m = map(int, input().split())
cave = []
for _ in range(n):
    tmp = []
    s = list(input())
    for c1 in s:
        if c1 == ".":
            tmp.append(0)
        else:
            tmp.append(1)
    cave.append(tmp)

input()
com = list(map(int, input().split()))
dr = [1,0,-1,0]
dc = [0,1,0,-1]
# main
for i in range(len(com)):
    find = False
    if i % 2 == 0:  # left
        row = n - com[i]
        idx = 0
        find = False
        while idx < m:
            if cave[row][idx] == 1:
                find = True
                break
            idx += 1
    else:
        row = n - com[i]
        idx = m-1
        find = False
        while idx >= 0:
            if cave[row][idx] == 1:
                find = True
                break
            idx -= 1

    if find:
        cave[row][idx] = 0
        for j in range(4):
            nr = row + dr[j]
            nc = idx + dc[j]
            if 0 <= nr < n and 0 <= nc < m:
                if cave[nr][nc] == 1:
                    bfs(nr, nc)


res = ""
for r_ in range(n):
    for c_ in range(m):
        if cave[r_][c_]:
            res += "x"
        else:
            res += "."
    res += '\n'

print(res)

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