[알고리즘] DFS with Python

💡 DFS 알고리즘

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

데이터의 갯수가 N개인 경우, O(N)의 시간복잡도를 가진다.

💡 DFS 동작과정

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

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

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

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

 

[참고]

그래프의 두 노드가 가나선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현한다.

DFS에서 인접한 노드가 여러개 일 수 있다. 그래서 스택에 어떠한 노드부터 방문할 것인지에 대한 기준이 필요하다. 이는 문제마다 다를 수도 있고 순서가 상관없을 수 있다. 현재 포스팅에서는 낮은 수부터 방문한다 가정한다.

💡 DFS 구현 코드

DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다.

실제 구현은 스택을 직접 사용하지 않고 재귀함수를 이용할 수 있다.

def dfs(graph, n, visited):
  # 현재 노드를 방문처리
  visited[n] = True
  print(n, end='')
  
  # 현재 노드와 인접한 노드를 확인
  for i in graph[n]:
    # 방문하지 않은 노드라면
    if not visited[n]:
      # 재귀호출
      dfs(graph, i, visited)

######## dfs 사용
# 각 노드에 연결된 정보를 2차원 리스트로 표현
graph =[
  [], # 노드번호가 1부터 시작하기 때문에 인덱스 0은 비워둔다
  [2,3,8], # 1번 노드와 인접한 노드 2,3,8
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

# 각 노드가 방문된 정보
visited = [False]*(8+1) # 전체 노드갯수 8개+인덱스0
# dfs 호출
dfs(graph, 1, visited)

 

💡 DFS 알고리즘 문제

Q1. 음료수 얼려 먹기

 N*M 크기의 얼음틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 갯수를 구하는 프로그램을 작성하시오. 

* 입력 조건

- 첫째줄에 얼음 틀의 세로 길이 N과 가로길이 M이 주어진다.(1<= N,M <= 1000)

- 둘째줄부터 N+1번째 줄까지 얼음틀의 형태가 주어진다.

- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

* 출력 조건

- 한번에 만들 수 있는 아이스크림의 갯수를 출력한다.

 

* 입력 예시

4 5

00110

00011

11111

00000

* 출력 예시

3

 

[문제 아이디어]

 '상,하,좌,우로 붙어 있는 경우 서로 연결되어있다고 간주한다'에서 DFS를 떠올릴 수 있었다. 동작과정은 다음과 같다.

1. 특정한 지점의 상, 하, 좌, 우를 살펴본 뒤에 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

(=방문하지 않은 인접노드가 있다면 방문한다.)

2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하면, 연결된 모든 지점을 방문할 수 있다.

3. 전체 얼음틀에 대해서 1~2를 반복하며 만들 수 있는 아이스크림의 갯수를 센다.

 

[코드]

구현시, visited 리스트가 굳이 필요하지 않다.

graph가 0, 1로만 이루어져있기 때문에 이를 visited로 사용할 수 있다.

# 세로n, 가로m
n, m = map(int, input().split())

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

# dfs로 특정한 방문한 뒤에 인접 노드들도 방문
def dfs(x,y):
  # 주어진 범위를 벗어날시에 종료
  if x<0 or y<0 or x>n-1 or y>m-1:
    return False

  # 방문할 수 있는 노드라면 방문
  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

  return False

# 아이스크림 수 세기
result = 0
for i in range(n):
  for j in range(m):
    # 현재 위치에서 DFS 수행
    # 애초에 1이였거나 방문하여 1이되었거나 범위를 벗어난 경우라면
    # false를 리턴한다.
    # 만약 True라면 이전에 방문하지 않은 새로운 아이스크림이다
    if dfs(i,j) == True:
      result +=1

print(result)

---

--> 추후에 추가예정

💡 DFS 관련 프로그래머스 문제

Q1. 왕실의 나이트

 

왕실 정원은 체스판과 같은 8*8좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다.  나이트는 이동할때 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1) 수평으로 두칸 이동한 뒤에 수직으로 한칸 이동

2) 수직으로 두칸 이동한 뒤에 수평으로 한칸 이동

 

이처럼 8*8좌표 평면상에서 나이트 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다. 예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 c2,b3 두가지 이다. c2에 위치해 있다면 경우의 수는 6가지 이다.

 

*입력조건

- 첫째줄에 8*8 좌표평면 상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두문자로 구성된 문자열이 입력된다. 입력문자는 a1처럼 열과 행으로 이뤄진다.

*출력 조건

- 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

 

*입력 예시

a1

*출력 예시

2

 

[문제 아이디어]

 시뮬레이션 문제유형이다. 상하좌우와 비슷한 문제인데, 좌표설정에서 차이가 있다.

아스키 코드로 'a'는 97 이고 'z'는 122임을 알아두자.

 

[코드]

position = input()

# 이동방향 정의
move_col = [2, 2, -2, -2, 1, 1, -1, -1]
move_row = [1, -1, 1, -1, 2, -2, 2, -2]

# 이동 가능한 방향의 갯수 구하기
count = 0
for i in range(len(move_col)):
  next_col = ord(position[0]) + move_col[i]
  next_row = int(position[1]) + move_row[i]

  # 해당 방향으로 이동 가능 여부
  if ord('a')<=next_col<=ord('h') and 1<=next_row<=8:
    count += 1

print(count)