[BOJ/백준 코딩] 인구 이동 - PYTHON #16234

소스 코드(pypy로 돌림)

def bfs(ii,jj):
    global idx

    while len(temp_idx) != 0:

        i, j = temp_idx.pop(0)

        for e in range(4):
            ni = i + x[e]
            nj = j + y[e]

            # index 범위 조건
            if 0 <= ni < n and 0 <= nj < n:

                # l 이상 r 이하 조건, 방문 조건
                if l <= abs(board[i][j] - board[ni][nj]) <= r and check[ni][nj] == -1:

                    # 연합이 된 위치의 값 더하고
                    temp_num[0] += board[ni][nj]

                    # 지금까지 연합의 개수 갱신
                    temp_num[1] += 1
                    temp_idx.append([ni, nj])

                    # 방문 및 나중에 store에서 값을 구해올 인덱스 값 저장
                    check[ni][nj] = idx

        # 연합한 적이 있으면
        if temp_num[1] > 1:

            # 시작 위치에도 인덱스 값 저장
            check[ii][jj] = idx

    # 연합한 적이 있으면
    if temp_num[1] > 1:

        # 연합의 평균 store[idx]에 저장
        store[idx] = int(temp_num[0] / temp_num[1])

        # 인덱스 갱신
        idx += 1

    return

# 좌 우 상 하
x = [0, 0, -1, 1]
y = [-1, 1, 0, 0]

n, l, r = map(int, input().split())

board = [list(map(int, input().split())) for _ in range(n)]

# 이동 횟수
cnt = 0

while True:

    # idx, store, check 초기화
    idx = 0
    store = [0] * (n * n // 2)
    check = [[-1] * n for _ in range(n)]

    for q in range(n):
        for w in range(n):

            # 방문한 적 없으면
            if check[q][w] == -1:
                temp_num = [board[q][w], 1]
                temp_idx = [[q, w]]
                bfs(q,w)

    # idx != 0은 연합한 적 있음을 의미
    if idx != 0:
        for qq in range(n):
            for ww in range(n):

                # 인덱스값 저장되어 있으면
                if check[qq][ww] != -1:

                    # board값 갱신
                    board[qq][ww] = store[check[qq][ww]]

    # 한 번이라도 연합한 적 없으면 끝내기
    else:
        break

    # 한바퀴 다 돌면 이동 횟수 + 1
    cnt += 1

print(cnt)

 

---

해결 방법

board

a	b
c	d

store

0

0

check

-1	-1
-1	-1

temp_num

a

1

idx = 0

 

1. board에서 시작 위치를 정한 후, 네 방향을 확인하면서 bfs 돌기

 

2. 연합이 되는 곳을 발견하면 check에서 같은 위치에 있는 값을 idx값으로 갱신해줌

 

2-1. 그 후, 해당 위치의 값(board)을 temp_num[0]에 더 해주고, temp_num[1]에 +1 해줌

 

3. bfs가 끝나고 temp_num을 이용해서 연합의 평균을 구하고, 이를 store[idx]에 저장

 

4. idx + 1해서 다음 연합은 다음 idx에 저장할 수 있도록 갱신

 

5. 반복

 

6. 다 끝난 후, idx값이 바뀌었으면(연합한 적이 한번이라도 있으면)

check를 돌면서 -1이 아니면 해당 위치의 값(idx)를 통해 store의 값을 찾고, 이를 통해 같은 위치의 board의 값을 갱신

---

느낀 점

1. python3으로는 아무리해도 해결이 안 되더라...(결국 pypy로 돌렸음)

 

2. 시간초과 문제를 해결하기 위해 append를 최소화할 수 있는 방법을 찾기 위해 노력

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.