dfs/bfs 유형(알고리즘, Python)

dfs, bfs 유형

이중 리스트로 visited나 grid 만들때

visited = [[False]*3]*3 

• 위와 같이 3x3 격자에 대한 visited 어레이를 만들면 안된다.
• [1,2,3]* 3 은 리스트 내부 원소를 3번 반복하라는 것인데 만약 안에 들어있는 것이 숫자가 아니라 리스트면 하나의 리스트를 변경하면 다른 리스트도 변경된다. 아마 리스트의 얕은 복사와 깊은 복사의 차이때문에 그런 듯 하다.
• 따라서 아래와 같이 리스트가 복사가 되지 않도록 해야한다.

visited = [[False]*3 for _ in range(3)]

visited = [[False for _ in range(3)] for _ in range(3)]

dfs

# dfs 문제 구현

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
grid = []
for i in range(n):
    grid.append(list(map(int, input())))

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


def dfs(x, y):
    if grid[x][y] == 0:
        grid[x][y] = 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx > (n-1) or ny < 0 or ny > (m-1):
                continue
            elif grid[nx][ny] == 1:
                continue

            else:
                dfs(nx, ny)
        return True

    else:
        return False

cnt = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            print(i, j)
            cnt += 1
print(cnt)

• 처음 넣어준 좌표로부터 시작해서 모든 순회가 끝났을 때(모든 재귀함수를 수행한 후,) return True를 해주는 것이 핵심.
• 좌표 벗어날 때의 범위 설정 해주는 것 주의
• 재귀함수 안의 함수의 리턴값이 어떻게 되던간에 마지막 재귀함수의 리턴값만 생각하면 된다.
• else return False는 안해줘도 상관없다.

bfs

# 최단거리 미로

from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
grid = []
for i in range(n):
    grid.append(list(map(int, input())))

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

visited = [[False for _ in range(m)] for _ in range(n)]
def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()
        if (x, y) == (n-1, m-1):
            break
        print((x,y))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>(n-1) or ny<0 or ny>(m-1):
                continue
            elif grid[nx][ny] == 0:
                continue
            else:
                if visited[nx][ny] == True:
                    print('a')
                    if grid[x][y]+1 < grid[nx][ny]:
                        grid[nx][ny] = grid[x][y]+1

                else:
                    print('b')
                    grid[nx][ny] = grid[x][y]+1
                queue.append((nx, ny))
                visited[nx][ny] = True
bfs(0,0)
print(grid)
print(grid[n-1][m-1])

• 다익스트라 비스무리하게 풀었는데 좀 어렵게 생각했던 것이다.
  다익스트라를 쓰려고 하다보니 해당 노드를 처음 방문하는 경우, 재방문하는 경우로 나누어서 처리해야했다.
• bfs자체가 시작노드부터 한단계씩 가까운 노드순으로 순회하는 것이기때문에 처음 방문하는 경우에 가장 최단경로로 온 것이다.
• 그러므로 아래와 같이 처음 방문일때의 경로길이만 반영하는 형태로 하면 훨씬 쉬운 풀이가 된다.

from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 벽인 경우 무시
            if graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1]

# BFS를 수행한 결과 출력
print(bfs(0, 0))

인구이동

# 인구이동 bfs
from collections import deque
from collections import defaultdict

n, l, r = map(int, input().split())
grid = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(n):
    grid.append(list(map(int, input().split())))

def bfs(x,y, start):
    visited[x][y] = start # visited에 시작노드기록
    dic1[start] += 1 # union의 국가수
    dic2[start] += grid[x][y] # union의 총합
    queue = deque([(x,y)])
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>(n-1) or ny<0 or ny>(n-1):
                continue
            # 값의 차가 범위 밖이라면
            elif abs(grid[x][y] - grid[nx][ny]) < l or abs(grid[x][y] - grid[nx][ny]) > r:
                continue
            else:
                if visited[nx][ny] == False:
                    visited[nx][ny] = start
                    queue.append((nx,ny))
                    dic1[start] += 1
                    dic2[start] += grid[nx][ny]

ans = 0
while True:
    visited = [[False for _ in range(n)] for _ in range(n)]
    dic = {}
    dic1 = defaultdict(int)
    dic2 = defaultdict(int)
    c = 0
    for j in range(n):
        for k in range(n):
            c -= 1
            if visited[j][k] == False:
                bfs(j, k, c)
    # 평균계산
    stop_cnt = 0
    for i in dic1:
        if dic1[i] == 1:
            stop_cnt += 1
        else:
            dic[i] = int(dic2[i]/dic1[i])
    if stop_cnt == n**2:
        break
    # print('dic', dic)
    
    # 평균으로 바꾸기
    for j in range(n):
        for k in range(n):
            if visited[j][k] in dic:
                grid[j][k] = dic[visited[j][k]]
    # print(grid)
    ans += 1

print(ans)

내가 한 방법
1. bfs로 순회해서 합쳐져야할 노드덩어리 파악하고 순회하면서 어떤 그룹인지 표시해놓고 해당 그룹의 노드갯수, 인구수총합 더해주기
2. 그룹평균구해서 해당 그룹에 속하는 노드값 바꾸기

python3로는 시간초과,,, pypy3는 가능했다.

python3로 푼 코드와 비교해보자

코드참고

from collections import deque

dxs = [-1, 0, 1, 0]
dys = [0, 1, 0, -1]

def bfs(x, y):
    visited = set([(x, y)])
    q = deque([(x, y)])

    """
    total : 연합의 인구수
    num : 연합에서 나라의 갯수
    """
    total, num = 0, 0

    while q:
        x, y = q.popleft()

        # 방문한 현재 나라의 인구수를 연합의 인구수에 더해주고, 연합에 속한 나라도 증가해준다.
        total += board[x][y]
        num += 1

        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy

            if nx >= 0 and nx < n and ny >= 0 and ny < n and (nx, ny) not in visited\
                and (nx, ny) not in total_visited:

                diff = abs(board[nx][ny] - board[x][y])
                if diff >= l and diff <= r:
                    # BFS를 한 번이라도 탄 것이므로, is_move를 True로 변환.
                    global is_move
                    is_move = True

                    q.append((nx, ny))
                    visited.add((nx, ny))

    # 이 연합의 바뀔 인구수와, 연합에 속한 나라(좌표)들을 반환한다.
    return total // num, visited

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

while True:
    total_visited = set() # BFS 탐색에 한번이라도 들어간 경우, 재 탐색을 할 필요가 없으므로,
                          # 이 집합에 담아둔다.
    is_move = False       # 한 번이라도 BFS를 타게되면 True로 바뀐다.
    unions = []           # (바뀔 인구수, 연합의 좌표들)을 담는다.

    # 먼저, 연합들을 찾아서 unions에 담는다.
    for i in range(n):
        for j in range(n):
            if (i, j) not in total_visited:
                changed_num, visited = bfs(i, j)
                unions.append((changed_num, visited))
                total_visited |= visited

    # 찾은 연합들의 좌표들을 일괄적으로 바꿔준다.
    for (changed_num, union) in unions:
        for country in union:
            x, y = country
            board[x][y] = changed_num

    # 한 번이라도 BFS를 타고들어갔는지 확인한다.
    if not is_move:
        break
    answer += 1

print(answer)

일단 중지조건이 다르다.
나는 1개 노드만 순회하는 횟수가 전체노드수와 같다면 멈춘다.
비교코드에서는 한번이라도 bfs를 타고들어가는지 bfs함수 내부에서 체크한다.

평균을 계산하는 것이 다르다.
bfs를 한번 돌때 union한개가 완성이 되기 때문에 bfs함수내에서 평균계산이 가능하다.
나는 그룹들을 딕셔너리에 넣고 나중에 평균계산을 했는데 이러면 반복문을 한번 더 쓰게 되고, 유니온이 많다면 훨씬 시간이 많이 걸리게 된다.~~

참고코드를 돌려보니 내 코드보다 시간, 공간 복잡도가 더 높았다.
해당 코드도 pypy3로 돌렸나보다,,,^_ㅠ....

내 생각도 옳다는 교훈을 얻었고,
python3로 풀 수 있는 방법이 있긴하지만 내 풀이가 제대로되지 않은 풀이법은 아니었다. 파이썬언어자체가 느려서 제대로 풀어도 이런 경우가 있다고 한다.