DFS와 BFS

『이것이 코딩 테스트다』 5장이다. 스택, 큐, 재귀, 그래프 표현 방식 예제를 따라 친 뒤 DFS 와 BFS 를 구현하고 음료수 얼려 먹기와 미로 탈출을 풀었다. 미로 탈출 풀이 끝에는 BFS 가 거리를 격자에 어떻게 적어 가는지 출력해 둔 것이 있다. DFS 예제에는 if not visited[v] 로 적어 둔 버그가 있다. 방문 여부를 확인할 것은 이웃 i 다. 특정 거리의 도시 찾기는 DFS 로 접근한 1차 풀이에서 멈췄다.

스택 예제

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop() #7
stack.append(1)
stack.append(4)
stack.pop() #4

print(stack) #가장 깊은 곳 부터 출력
print(stack[::-1]) #pop되면서 출력

큐 예제

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
# queue.pop() # 7
queue.popleft() # 5
queue.append(1)
queue.append(4)
queue.popleft() # 2

print(queue) # 입력한 순서대로

queue.reverse()
print(queue)

# pop 최근 들어온 것
# popleft 먼저 들어온 것

재귀 예제

def recursive_function(i):
    if i == 100:
        return
    print(f'{i}번째 재귀 함수를 호출합니다')
    recursive_function(i+1)

recursive_function(1)

팩토리얼 예제

# 반복적으로 구현
def factorial_iterative(n):
    result = 1
    for i in range(1,n+1):
        result *= i
    return result

def factorial_recursive(n):
    # if n == 1:
    #     return

    # 1! 0! 인 경우도 계산해야 하기 때문에
    if n <=1 :
        return 1

    return n*factorial_recursive(n-1)


# 재귀로 구현

print(factorial_iterative(5))
print(factorial_iterative(5))

그래프 표현 방식

#인접행렬(Adjacency Matrix)
INF = 999999999

graph = [
    [0,7,5],
    [7,0,INF],
    [5,INF,0]
]

print(graph)
# 인접 리스트(Adjacency List)
graph = [[] for _ in range(3)]

graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))

graph[2].append((0,5))

print(graph)

DFS 예제

def DFS(graph,v,visited):
    visited[v] = True
    print(v,end='')

    for i in graph[v]:
        if not visited[v]:
            DFS(graph,i,visited)

graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9
DFS(graph,1,visited)

BFS 예제

from collections import deque

def BFS(graph,start,visited):
    queue=deque([start])
    visited[start]=True
    while queue:
        v=queue.popleft()
        print(v,end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

graph=[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9
BFS(graph,1,visited)

음료수 얼려 먹기

# 영역별 카운트가 필요함
# 아이디어: 카운트는 vistied ==False일 때만 시키고,
# visited Ture일 때 연결되어 있는 노드들은 연쇄적으로 True로 만들어 버려서 카운트 되지 않게 하기

n,m = map(int,input().split())

graph=[]
for i in range(n):
    graph.append(list(map(int,input())))

#DFS로 연결된 노드 방문
# index error는 len(array) 이상일 때만, -1은 순서 뒤로 가느 인덱스!!
# def DFS(x,y):
#     try:
#         if graph[x][y] ==0:
#             graph[x][y] = 1
#             DFS(x-1,y)
#             DFS(x+1,y)
#             DFS(x,y-1)
#             DFS(x,y+1)
#             return True
#         else:
#             return False
#     except:
#         pass

def DFS(x,y):
    # if x > -1 or x<n and y>-1 or y<m:
    # 여집합
    if x > -1 and x<n and y>-1 and y<m:
        if graph[x][y] == 0:
            graph[x][y] = 1
            DFS(x-1,y)
            DFS(x+1,y)
            DFS(x,y-1)
            DFS(x,y+1)
            return True
        else:
            return False
    else:
        return

result = 0

for i in range(n):
    for j in range(m):
        if DFS(i,j) == True:
            result +=1

print(result)

미로 탈출

#BFS풀이: 시작지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문
from collections import deque

n,m=map(int,input().split())
graph=[]
for i in range(n):
    graph.append(list(map(int,input())))
    # list(iterative)이므로 input의 한 음절씩 int로 바뀌어 list로 들어가게된다.

# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def BFS(x,y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            # 공간을 벗어낫거나, 벽인 경우는 continue로 바로 다음 반복 문으로 이동
            if nx<0 or nx>=n or ny<0 or ny>=m or graph[nx][ny]==0:
                continue
            elif graph[nx][ny] ==1: # 0이면 못가는 곳, 2이상이면 이미 방문했던 곳, 딱 1이여야 다음칸으로 이동할 수 있음
                graph[nx][ny] = graph[x][y] + 1 # 한 칸 이동 했음을 표시
                queue.append((nx,ny)) # 현재 이동한 곳이 다음 출발지점이 됌
    return graph[n-1][m-1]

print(BFS(0,0))
for i in range(n):
    print(graph[i])


# [3, 0, 5, 0, 7, 0]
# [2, 3, 4, 5, 6, 7]
# [0, 0, 0, 0, 0, 8]
# [14, 13, 12, 11, 10, 9]
# [15, 14, 13, 12, 11, 10]
# [1,0]에서 상으로 이동할 때 1+2가 되버리기 때문에 3이 됌

특정 거리의 도시 찾기 (1차 풀이에서 멈춤)

# 1차 풀이
# default dict로 사용하는건 DFS안에 for문에서 방문처리할 때.. 가 아니라 단방향거리만 존재니까 다시해보자
from collections import defaultdict
di=defaultdict(list)

n,m,k,x = map(int,input().split())

# 빈 리스트로 초기화
for i in range(1,n+1):
    di[i]

# 유사 딕셔너리로 값 대입
for i in range(m):
    li=list(map(int,input().split()))
    di[li[0]].append(li[1])

count = -1
answer = []
def DFS(x,di,k,count):
    # 최단거리가 같을 때
    global answer
    if k == count:
        answer +=1
        return
    # 다음에 방문할 곳이 있다면
    if di[x] != []:
        for i in di[x]:
            DFS(i,di,k,count+1)
    return

DFS(x,di,k,0)

print(i for i in answer if answer ==[])