[DFS/BFS] (백준) 인구이동 - 파이썬

✅ 쓸데없는 checked함수를 만들었음 => DFS에서 이동이 일어났는지를 moved로 flag를 만들고 이후 이동이 없으면 끝내는 방식을 써야함 / checked함수만든이유? 확인은 해야한다고 생각해서 만들었는데 DFS에서 확인할 수 있다는 걸 놓친것 같음. 어떤 과정이 다른 과정에 포함될 수 있는지를 한번 더 생각해보자

✅ path에 처음 자기자신이 포함이 되어야한다는 점과 그래서 이동이 일어나면 길이가 1보다 커야한다는 점을 놓침 => 자기자신도 넣어야하는 경우와 해당 기능과 연관된 기능을 한번 더 꼼꼼히 살펴보자

✅ DFS에서 재귀오류가뜸 => stack을 활용하거나 BFS를 사용하거나하면됨. stack으로 DFS를 구현할 수 있다는 점이 신기했음

✅ 예시가 하나밖에 없을때 얼른 하나 만들어서 확인해보는 방법도 있음(도저히 어디가 틀렸는지 모르겠을때)

def dfs(r, c):
    global visited, path, tot
    stack = [(r, c)]
    while stack:
        r, c = stack.pop()
        for d in range(4):
            nr, nc = r + dr[d], c + dc[d]
            if not (0 <= nr < N and 0 <= nc < N) or visited[nr][nc] == 1:
                continue
            if L <= abs(data[nr][nc] - data[r][c]) <= R:
                visited[nr][nc] = 1
                path.append((nr, nc))
                tot += data[nr][nc]
                stack.append((nr, nc))



N,L,R = map(int,input().split())
data = [list(map(int, input().split())) for _ in range(N)]
dr = [-1,0,1,0]
dc = [0,1,0,-1]
answer = 0

while True:
    visited = [[0]*N for _ in range(N)]
    moved = False
    for i in range(N):
        for j in range(N):
            if visited[i][j]!=1:
                visited[i][j]=1
                path = []
                path.append((i,j))
                tot = data[i][j]
                dfs(i,j)
                if len(path)>1:
                    moved = True
                    new_pop = tot//len(path)
                    for r,c in path:
                        data[r][c]=new_pop
    if moved :
        answer+=1
    else:
        print(answer)
        break

# 4 10 40
# 10 20 25 90
# 40 30 30 35
# 10 80 30 75
# 10 80 30 35
# 정답 : 4