Python | 깊이/너비 우선 탐색(DFS/BFS)

Breadth First Search (BFS)

> Level 별로 탐색

> 그래프가 딕셔너리 형태로 key는 node, value는 연결된 모든 node를 나열하는 경우, 아래와 같은 방식으로 해결할 수 있습니다.

 

# 기본 방식

문제를 풀어보면서 많이 느낀 부분은 기본 구조를 정확히 익히는게 중요하다고 생각이 들었습니다.

말 그대로, 그래프를 깊이 우선이든, 너비 우선이든 다 탐색하는 것이기 때문에 visited라는 부분을 설정하고 점검하는 부분이 중요하고, queue를 사용함에 있어 initial 값을 넣고 popleft로 값을 뺐다가 추가로 다음 값을 넣는 부분을 생각해서 풀어야 한다는 것을 문제를 여러 개 풀면서 점점 익히는 것 같습니다. 

from collections import deque

def bfs(graph, start_v):
    visited = [start_v]
    queue = deque(start_v)
    while queue:
        cur_v = queue.popleft()
        for v in graph[cur_v]:
            visited.append(v)
            queue.append(v)
    return visited

from collections import deque

def bfs(grid):
    def isValid(r, c):
        return (
            (r >= 0 and r < row_len)
            and (c >= 0 and c < col_len)
            and grid[next_r][next_c] == 1
        )
    row_len, col_len = len(grid), len(grid[0])
    visited = [[False] * col_len for _ in range(row_len)]
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]

    queue = deque()
    queue.append(0, 0)
    visited[0][0] = True
    while queue:
        cur_r, cur_c = queue.popleft()
        for i in range(4):
            next_r = cur_r + dr[i]
            next_c = cur_c + dc[i]
            if isValid(next_r, next_c):
                if not visited[next_r][next_c]:
                    queue.append((next_r, next_c))
                    visited[next_r][next_c] = True

 

# 프로그래머스 | 단어 변환

from collections import deque

def solution(begin, target, words):
    
    if not target in words:
        return 0
    
    answer = 0
    v = [0] * len(words)
    q = deque()
    q.append([begin, 0])

    while q:
        word, cnt = q.popleft()
        if word == target:
            return cnt
        for i in range(len(words)):
            tmp_cnt = 0
            if not v[i]:
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        tmp_cnt += 1
                if tmp_cnt == 1:
                    q.append([words[i], cnt+1])
                    v[i] = 1
                        
    return answer

 

# 프로그래머스 | 여행경로

from collections import deque

def solution(tickets):
    q = deque()
    answer = []
    start = "ICN"
    q.append([start, 0, [start], [False] * len(tickets)])
    
    while q:
        stp, cnt, path, used = q.popleft()
        
        if len(tickets) == cnt:
            answer.append(path)
            continue
           
        for i in range(len(tickets)):
            s, d = tickets[i]
            if s == stp and not used[i]:
                new_used = used[:]
                new_used[i] = True
                new_path = path + [d]
                q.append([d, cnt+1, new_path, new_used])
        
    answer.sort()
    return answer[0]

 

# 프로그래머스 | 아이템 줍기

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    
    # 1~50이하 자연수 범위이며, 직사각형이 50% 차지하는 경우가 있기에 넉넉히 102로 계산
    mapxy = [[-1]*102 for _ in range(102)]
    visited = [[False]*102 for _ in range(102)]
    
    dx, dy = [0,1,0,-1], [1,0,-1,0]
    q = deque()
   
    # 2배로 해서 굵은 선이 아닌 직사각형 바로 옆 테두리로 이동하는 걸 차단
    cx, cy, ix, iy = characterX*2, characterY*2, itemX*2, itemY*2
    visited[cx][cy] = True
    q.append((cx,cy))
    
    for r in rectangle:
        x1,y1,x2,y2 = map(lambda x:x*2, r)
        
        # 테두리 1, 내부 0, 외부 -1
        for i in range(x1,x2+1):
            for j in range(y1,y2+1):
                # 테두리 제외 내부만 0으로
                if x1<i<x2 and y1<j<y2:
                    mapxy[i][j] = 0
                # 테두리만 1
                elif mapxy[i][j] != 0:
                    mapxy[i][j] = 1
        
    while q:
        x, y = q.popleft()        
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if 0<=nx<102 and 0<=ny<102:
                if mapxy[nx][ny] == 1 and not visited[nx][ny]:
                    visited[nx][ny] =True
                    q.append((nx,ny))
                    mapxy[nx][ny] = mapxy[x][y]+1
    
    # 전체를 2배 해서 계산했기 때문에 1/2
    return mapxy[ix][iy] //2