주요 알고리즘(3)-DFS/BFS

• DFS

깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

1.탐색 시작 노드를 스택에 삽입하고 방문처리를 한다

2.스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다.

방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 1,2번 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

 

#dfs 메서드 정의
def dfs(graph, v, visited):
  visited[v] = True #현재 노드 방문 처리
  print(v, end=' ')

  for i in graph[v]: #현재 노드와 연결된
    if not visited[i]:
      dfs(graph, i, visited)
graph=[[], #2차원 리스트 자료형으로 표현
      [2,3,8], #1번 노드 연결 정보
      [1,7], #2번 노드 연결 정보
      [1,4,5],
      [3,5],
      [3,4],
      [7],
      [2,6,8],
      [1,7]
      ]
visited=[False]*9

dfs(graph,1,visited)

 

• BFS

너비우선탐색, 가까운 노드부터 탐색하는 알고리즘으로 선입선출 방식인 큐 자료구조를 이용하는 것이 정석

 

1.탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼내 해당 노드의 인접노드중 방문 하지 않은 노드를 모두 큐에 삽입하고 방문 처리

3. 1,2,번과정을 수행할 수 없을 때 까지 반복

 

 

from collections import deque  #queue사용을 위한 모듈


def bfs(graph, start, visited): #BFS 메서드 정의
    queue = deque([start]) #큐 구현을 위해 deque 사용
    visited[start] = True #방문한 노드를 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차원 리스트 자료형으로 표현
  [2,3,8], #1번 노드 연결 정보
  [1,7], #2번 노드 연결 정보
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
  ]

visited=[False]*9

 

bfs(graph, 1, visited)

 

---

• 음료수 얼려 먹기

NXM의 얼음 틀이 있고 구멍이 뚫린부분은 0, 칸막이가 있는 부분은 1로

구멍이 뚫린부분이 상,하,좌,우 로 붙어있는 경우 서로 연결되어있는것으로 간주한다.

얼음 틀 모양을 입력받고 생성될 수 있는 총 아이스크림의 개수를 구하시오

 

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

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

def dfs(x, y):
  if x<=-1 or x>=n or y<=-1 or y>=m:
    return False
  if graph[x][y] == 0:
    graph[x][y] = 1
    dfs(x-1, y) #왼쪽 탐색 'L'
    dfs(x, y-1) #아래 탐색 'D'
    dfs(x+1, y) #오른쪽 탐색 'R'
    dfs(x, y+1) #위쪽 탐색 'U'
    return True
  return False

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

print(result)