글 읽기 - 문제 이해가 안 갑니다..

rlarudans134 2년 전 0

저는 그냥 연합 수를, 연합으로 이루어진 국가들의 인구 수를 모두 더한 값에 나눠주고, 이렇게 나온 값으로 연합으로 된 국가들 각각의 인구를 다시 바꿔주면 되는 것으로 이해하고 있습니다..

나머지 테스트케이스는 잘 나오는데, 마지막 테스트 케이스가 2로 출력이 됩니다.. 마지막 예제를 돌리면 나오는 결과를 넣어놓겠습니다

이동 전) (초기값)

[[10, 100, 20, 90], [80, 100, 60, 70], [70, 20, 30, 40], [50, 20, 100, 10]]

첫 번째 bfs 수행 후)

result : deque([80, 70, 100, 50, 20, 60, 20, 20, 30, 70, 90, 40, 10])
up ---> 50

첫 번째 인구 이동 후)

[[10, 100, 50, 50], [50, 50, 50, 50], [50, 50, 50, 50], [50, 50, 100, 50]]

두 번째 bfs 수행 후)

result : deque([10, 50, 100, 50, 50, 50, 100, 50, 50])
up ---> 56

두 번째 인구 이동후)

[[56, 56, 56, 50], [56, 56, 50, 50], [50, 50, 56, 50], [50, 56, 56, 56]]

3 번째 bfs 수행 후) -> 연합이 존재 하지 않음

result : deque([])

결과 출력)

2

import sys
from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(y, x, visit):

    visit[y][x] = True
    queue = deque()
    queue.append([y, x])

    while queue:
        y, x = queue.popleft()
        for v in range(4):

            nx = x + dx[v]
            ny = y + dy[v]

            if 0 <= nx < length and 0 <= ny < length:
                flag = False
                if not visit[ny][nx]:
                    queue.append([ny, nx])
                    visit[ny][nx] = True
                # print("first get ----> ", graph[y][x])
                if not get[y][x]:
                    flag = True
                    result.append(graph[y][x])
                    get[y][x] = True

                if more <= abs(graph[y][x] - graph[ny][nx]) <= less:
                    if not get[ny][nx]:
                        # print("second get ----> ", graph[ny][nx])
                        result.append(graph[ny][nx])
                        get[ny][nx] = True
                elif flag:
                    # print("pop ---> ", graph[y][x])
                    result.pop()
                    get[y][x] = False


length, more, less = map(int, sys.stdin.readline().split())
graph = []
result = deque()
cnt = 0

for i in range(length):
    graph.append(list(map(int, sys.stdin.readline().split())))

while True:
    check = [[False] * length for i in range(length)]
    get = [[False] * length for i in range(length)]
    print(graph)
    bfs(0, 0, check)
    print("result :", result)

    if not result:
        break
    cnt += 1

    update = sum(result) // len(result)
    print("up ---> ", update)

    for y in range(length):
        for x in range(length):
            if get[y][x]:
                graph[y][x] = update
    result.clear()

print(cnt)

djm03178 2년 전 0

두 번째 이동 후가 이상하네요. [0][0]과 [1][0]은 둘끼리만 연합이 되어야 하는데 주변과도 연합이 된 것 같습니다.

rlarudans134 2년 전 0

제가 연합이 2개, 3개 만들어지는 경우를 그냥 뇌 속에서 빼고 한 것 같습니다... 답변 정말 감사드립니다

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