16234

날짜 : 2023. 03. 07

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

n, l, r = map(int, sys.stdin.readline().split())
land = list()
for _ in range(n):
    land.append(list(map(int, sys.stdin.readline().split())))
res = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(row, col, a, b):
    move = False
    q = deque()
    q.append([row, col])
    guild = deque()  # 연합
    guild.append([row, col])
    total = land[row][col]  # 연합 인구 수
    while q:
        x, y = q.popleft()
        for i in range(4):  # 인접마을
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(n) and ny in range(n):  # 마을 범위에 있고
                # 방문하지 않았고 연합인 경우
                if a <= abs(land[x][y] - land[nx][ny]) <= b and not visited[nx][ny]:
                    move = True  # 이동 발생
                    visited[nx][ny] = True  # 방문처리
                    q.append([nx, ny])  # 추가
                    guild.append([nx, ny])  # 길드에 추가
                    total += land[nx][ny]  # 총 인구수 갱신

    total = int(total // len(guild))
    #print(guild)

    while guild:
        i, j = guild.popleft()
        land[i][j] = total  # 인구이동
    """for i in land:
        print(i)
    print()"""
    return move


while True:
    flag = False
    visited = [[False] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:  # 연합체크 안했다면
                visited[i][j] = True
                temp = bfs(i, j, l, r)  # 확인
                if temp: flag = temp
    if flag:
        res += 1
    else:
        break

print(res)

 

 

풀이

- while문을 돌리고 그 안에서 BFS를 구현하여 문제를 풀이한다.

- 이중 for문에서 연합탐색 여부를 체크하고 탐색하지 않았다면 BFS에 진입한다.

- 기본 BFS와는 다르게 연합의 인구를 최신화해야 하기 때문에 guild라는 리스트를 추가하여 해당 위치를 저장, 방문처리 및 인구수를 최신화한다.

- 그리고 인구이동이 일어난 경우 True를 반환, 결과값을 1 증가시킨다.

 

 

알게된 점

- visited 없이 문제를 풀었을 때는 메모리 초과가 발생했다. 지나치게 탐색을 많이 했기 때문에 발생한 듯 했다.

- 이후에 계속 실패가 나와서 풀이를 보았고 visited를 활용해서 풀이하면 되는 것을 확인했다.

- 그런데 Bool 변수를 리턴하는 과정에서 예제 3의 값이 계속 0이 나와 무엇이 문제인지 계속 확인하느라 시간을 많이 할애했다. (flag값에 True를 리턴해도 마지막에 False를 리턴받으면 결국 res값은 조건문 때문에 증가하지 않는다.)

- 접근방식은 간단했지만 각 조건들을 빠짐없이 잘 확인해야 문제를 해결할 수 있다는 것을 느끼게 해준 문제였다.

 

 

참고 사이트

-