[알고리즘] BFS/DFS 문제 풀이 _ 파이썬

▒ 코딩테스트 공부 방법

 

 

  1. codeup 기초 100제로 기초를 다지고 사용할 언어에 익숙해지도록 한다. 

 

  2. 백준온라인 저지 단계별, 유형별 문제를 푼다.

배열, 문자열, 정렬, 브루트포스(완전탐색), 재귀, 백트래킹, 동적계획법, bfs/dfs 등의 유형에 익숙해진다.

-완전탐색(재귀나 백트래킹으로)->시뮬레이션->그래프(위상정렬, 다익스트라..)->최소신장유니온트리(유니온파인드 등)->심화문제(스택으로 라인스위핑 같은)->DP, dp는 코딩테스트에 나오면 완죠니 어렵게 나온다고 한다.

 

  3. 프로그래머스 코딩테스트 고득점 kit를 푼다.

유형별 4~7문제를 풀며 자주 나오는 유형을 익힌다.

 

  4. 프로그래머스 스킬체크

주어진 시간내에 2문제를 풀고, 나의 실력을 파악한다. 레벨3정도면 웬만한 코딩테스트에 합격할 수 있다고 한다.

 

 

 

---

 

 

 

저번 포스팅들에서 bfs, dfs 개념에 대해 정리를 했었고 이번에는 실전 문제 몇 개 푼거 코드를 리뷰해보려고 합니다.

먼저 쉬운 문제 위주로 풀었고, 되도록 재귀를 사용하지 않았다. 

 

항상 되새길 것은,

bfs, dfs 둘 다 모든 경로 탐색에 사용하고 bfs는 최단을 보장하나 dfs보다 메모리를 많이 사용한다. 그래서 백트래킹은 일반적으로 dfs를 통하여 구현한다.

---

 

※ BFS/DFS 문제 파이썬으로 풀 때 주의 할 점.

 

- 재귀로 풀 경우 재귀 깊이를 지정해주어야 한다.

import sys
sys.setrecursionlimit(100000)

- 파이썬의 리스트는 스택처럼 동작하므로 dfs 구현시 그냥 리스트를 사용하면 된다.

 

- bfs구현시 덱(deque)를 사용한다. (리스트로 .pop(0) 해도되지만 덱이 훨 빠르다.)

from collections import deque
q = deque()
print(q) # []
qq = deque([1])
print(qq) # [1]

 

- 방문했던 노드를 기록할 때 리스트보다 딕셔너리로 구현해야 빠르다. 또는 인덱스를 이용해 0,1을 넣어주거나 하면 된다.

# 예를 들어,
visit = [1,2,3]
if 4 in vitsited:
	pass
# 위와 같은 코드는, visit의 모든 노드를 살펴보아야함 O(N)

# 노드의 수가 5라고 하면
visit = [0]*5
if visit[4] == 1:
	pass
# 이런 식으로 인덱스를 지정하여 방문 노드를 검사하거나 딕셔너리를 이용한다.
# 기본적이지만 막 풀다보면 리스트를 남용해버리는 경우가 많다.

 

- 그래프는 인접 행렬로, 인접 리스트로 구현 할 수 있다. 전자는 리스트로 후자는 딕셔너리로 주로 구현한다.

 

 

---

 

푼 문제는,

백준 1012, 백준 1260, 백준 1697, 백준 2178, 백준 2667, 백준 6603, 백준 111724

 

 

1. 백준 1012

 

이 문제의 주의할 점은, 입력 받은 x 값은 가로 축을 나타내므로 '열(column)' 이다.

배추 밭을 입력 받은 후, 모든 요소를 순회하고 1을 만나면 완전탐색을 실시한다. bfs나 dfs 상관 없지만, dfs가 메모리를 더 적게 소모한다.

 

이런 문제의 팁은 dfs를 실시하는 순간 count++를 해주는 것이다.

 

1) for i~ for j~ 이중 포문으로 리스트 내 요소를 모두 탐색하기 시작한다.

2) 배추밭(lis)의 값이 1 이면, lis[i][j] == 0 이면 방문했다는 표시로 lis[i][j] = -1로 바꾸어준다.

3) 배추밭(lis)의 값이 1 이면, lis[i][j] == 1 이면 count를 +1해주고 완전 탐색을 실시한다. (dfs(lis, i, j))

4) i, j 값을 스택에 넣고 상, 우, 좌, 하를 순회하며 탐색한다.

5) i, j의 인접요소(상,우,좌,하) 중 값이 1인 경우 stack에 좌표 값(x,y)을 넣고 방문했다는 표시로 lis[x][y]를 -1로 바꿔준다.

6) i, j의 인접요소(상,우,좌,하) 중 값이 0이거나, -1인 경우 아무것도 하지 않고, 스택에 값이 없으면 dfs를 빠져나간다.

 

 

코드

import sys
input = sys.stdin.readline
from collections import deque

for _ in range(int(input())):
    m, n, k = map(int, input().split())

    lis = [[0]*m for i in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        lis[y][x] = 1
    count = 0

    def dfs(lis, i, j):
        dx = [0,0,1,-1]
        dy = [1,-1,0,0] # 우, 좌, 하, 상
        stack = [[i,j]]
        
        while stack:
            a, b = stack.pop()
            lis[a][b] = -1
            for i in range(4):
                x = a + dx[i]
                y = b + dy[i]
                if 0 <= x < n and 0 <= y < m and lis[x][y] == 1:
                    lis[x][y] == -1
                    stack.append([x,y])

    
    for i in range(n):
        for j in range(m):
            if lis[i][j] <= 0:
                lis[i][j] = -1
            else:
                count += 1
                dfs(lis, i, j)

    print(count)

 

---

 

2. 백준 2667

 

위 1012번과 비슷한 문제다. 묶음의 수만 출력하는 것이 아니라 묶음 안의 요소의 수/..? 를 출력하는 문제이다. 위에는 따로 result용 변수를 만들지 않아도 됬지만, 이번 문제에서는 result를 딕셔너리로 만들고, 몇번째 묶음인지: [요소의 좌표들] 기록했다. 푸는 방법은 여러가지지만 유니온파인드로 풀어보는 것도 나쁘지 않을 것 같다.

 

1) 모든 요소를 순회한다.

2) 요소의 값이 0이면, 방문했다는 표시로 -1을 기록해준다.

3) 요소의 값이 1이면, count ++ 후 dfs 실시

4) 상, 하, 좌, 우 값 탐색하고 방문하지 않았고, 값이 1이면 스택에 넣고, 결과 딕셔너리에 count를 키값으로하고, 좌표를 value로 남겨준다.  방문한 기록 -1 표시도 해준다.

 

예를 들어

0	0	1	0
1	0	0	1
1	0	1	0

이런 리스트가 있다고 치자, 인접한 요소(상우좌하)가 1이면 묶어준다.

result = {1:[[1,0], [2,0]], 2:[[0,2]], 3:[[1,3]], 4:[[0,3]]}

 

 

코드

import sys
input = sys.stdin.readline

n = int(input())
lis = []

for _ in range(n):
    tmp = []
    for t in list(map(str, input().strip())):
        tmp.append(int(t))
    lis.append(tmp)

def dfs(lis, i, j):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    stack = [[i,j]]
    result.setdefault(count,[[i,j]])

    while stack:
        a, b = stack.pop()
        lis[a][b] = -1
        for i in range(4):
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < n and 0 <= y < n and lis[x][y] == 1:
                result[count].append([x,y])
                lis[x][y] = -1
                stack.append([x,y])


count = 0
result = {}

for i in range(n):
    for j in range(n):
        if lis[i][j] == 0:
            lis[i][j] = -1
        if lis[i][j] == 1:
            count += 1
            dfs(lis, i, j)

print(len(result))
total = []
for key in result:
    total.append(len(result[key]))

total.sort()
for t in total:
    print(t)

 

 

 

---

 

3. 백준 1260

 

완전 기본 문제이고, 그래프가 주어지고 dfs, bfs로 방문한 노드를 순서대로 출력하는 문제이다.

스택과 큐를 사용하였고, 인접 행렬(리스트)로 구현하였을 경우와 인접 그래프(딕셔너리)로 구현하였을 경우의 시간을 비교해보았다.

 

코드_인접행렬

import sys
input = sys.stdin.readline
from collections import deque


def dfs(graph, v):
    visited = []
    stack = [v]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            stack += reversed(graph[n])
    return visited

def bfs(graph, v):
    visited = []
    queue = deque([v])
    
    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n]
    return visited

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

graph = {i:[] for i in range(1,n+1)}
for i in range(1, m+1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for key in graph:
    graph[key].sort()

print(' '.join(list(map(str,dfs(graph, v)))))
print(' '.join(list(map(str,bfs(graph, v)))))

 

 

코드_인접리스트

import sys
input = sys.stdin.readline
from collections import deque


def dfs(graph, v):
    visited = {}
    stack = [v]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.setdefault(n)
            stack += reversed(graph[n])
    return visited

def bfs(graph, v):
    visited = {}
    queue = deque([v])
    
    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.setdefault(n)
            queue += graph[n]
    return visited

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

graph = {i:[] for i in range(1,n+1)}
for i in range(1, m+1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for key in graph:
    graph[key].sort()

print(' '.join(list(map(str,dfs(graph, v)))))
print(' '.join(list(map(str,bfs(graph, v)))))

위가 인접리스트로 구현한 것이고 딕셔너리가 역시 빠르다.

 

 

---

 

 

4. 백준 1697

 

수빈이가 점 N에 있고 동생이 K에 있다. 이동은 1초에 +1, -1, *2 이동이 가능하다 가장 짧은 시간에 도착.

딕셔너리로 인접 리스트를 만들어서 구현했다. 수빈이가 처음 있는 점이 5라고 할 때, 1초 뒤에 4, 6, 10 으로 이동할 수 있고 그 값들을 큐에 넣고 K를 만날 때까지 반복. 최소 시간을 구하는거기 때문에 bfs를 사용해야 한다.

(이 문제는 경우의수, 완전탐색에 관한 문제로 브루트포스, 비트마스크, 순열, 백트래킹, bfs로 풀 수 있다)

 

 

단순하게 모든 경우의 수를 다 하니까 런타임에러가 났다. 경우에 따라 잘라주어야 한다. 예를들어 어떤 방법은 1부터 11까지 5초 만에 방문 했는데 다른 방법은 6초 만에 방문했다면 그 이후 노드는 보지 않아야 한다. 이런 방법을 백트래킹 이라고 하는데, 백트래킹은 조건에 따라 보지 않아도 될 것을 쳐내는 작업이다.

 

 

코드

import sys
input = sys.stdin.readline
from collections import deque

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

max = 100001
visited = [-1]*max
visited[n] = 0

q = deque([n])

while q:
    cur = q.popleft()
    if cur == k:
        print(visited[cur])
        sys.exit()

    for adj in [cur*2, cur+1, cur-1]:
        if 0 <= adj < max and visited[adj] == -1:
            visited[adj] = visited[cur] + 1
            q.append(adj)

bfs는 1초에 방문할 수 있는 모든 경우의 수 -> 2초 -> 3초... 이런식으로 순회하기 때문에 a~b까지 가는 경로들 중 먼저 발견되는 것이 가장 빠른 경우이다.

 

 

---

 

5. 백준 2178

 

미로 탐색, 지나야 하는 최소 칸 수..! 최소 칸 수니까 BFS로 풀고 그래프 탐색 문제임.

1	0	1	1
1	0	1	1
1	1	1	1

이런 미로가 있따면,

 

1	0	0	0
1	0	0	0
1	1	1	1

이렇게 지나가야 최소 경로.

 

1) 맨 처음 시작 노드 0,0 을 큐에 넣어준다.

2) 큐에서 팝한 노드의 상, 우, 좌, 하 값이 1인 경우 거기까지 온 거리를 visited에 기록해준다.

 

그러면 위의 예시로 그려논 미로의 경우 visited 는 이렇게 될 것이다.

1	0	7	8
2	0	6	7
3	4	5	6

 

 

코드

import sys
input = sys.stdin.readline
from collections import deque


def dfs(lis,n,m):
    dx = [0,0,0,1,-1]
    dy = [0,1,-1,0,0]
          #우,좌,하,상
    q = deque([[1,1]])
    visited = [[0]*(m+1) for _ in range(n+1)]
    visited[1][1] = 1

    while q:
        a,b = q.popleft()
        if a == n and b == m:
            print(visited[n][m])
            sys.exit()
        for i in range(1,5):
            x = a + dx[i]
            y = b + dy[i]
            if n >= x > 0 and m >= y > 0:
                if int(lis[x][y]) == 1 and visited[x][y] == 0:
                    visited[x][y] = visited[a][b] + 1
                    q.append([x,y])

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

lis = [[0]*(m+1)]
for _ in range(n):
    tmp = [0] + list(input())[:m]
    lis.append(tmp)

dfs(lis, n, m)

 

---

 

6. 백준 6603

 

1~49까지의 수 중 K개를 뽑고, 그 중 6개의 숫자를 뽑는 모든 경우의 수를 출력하는 문제

조합 문제이기 때문에 파이썬의 itertools.combinations를 사용하면 편하고 빠르고 좋지만

가끔 사용이 안되는 코딩테스트가 있다고 한다..? 잘모름

 

코드_itertools.combinations

import sys
input = sys.stdin.readline
from itertools import combinations


while True:
    case = list(input().split())
    if case[0] == '0': break

    for result in combinations(case[1:], 6):
        print(' '.join(result))
    print()

 

코드_dfs백트래킹

def dfs_comb(lis, n):
    stack = []
    result = []
    for i in range(len(lis)-1):
        stack.append([i])
    
    while stack:
        cur = stack.pop()
        if len(cur) != n:
            for i in range(cur[-1]+1,len(lis)):
                tmp = cur + [i]
                stack.append(tmp)
        else:
            result.append(cur)
    result.sort()
    return result


while True:
    case = list(input().split())
    if case[0] == '0': break
    case = case[1:]
    for line in dfs_comb(case, 6):
        for comp in line:
            print(case[comp], end=' ')
        print()
    print()

위가 dfs백트래킹으로 푼 것이고 아래가 itertools.combinations를 사용한 것임.

 

---

 

7. 백준 11724

 

그래프의 노드와 간선 그리고 연결된 노드들이 주어졌을 때 연결요소의 개수를 구하는 문제이다. dfs, bfs로 구현이 가능하다. 유니온 파인드로도 풀 수 있다.

 

나는 주어진 노드들로 일단 인접리스트를 만들었고, 방문하지 않았던 노드를 탐색하는 순간 count+1 해주고 인접한 리스트를 모두 방문하고 -1 해주고 다시 돌아온다.

 

코드

import sys
input = sys.stdin.readline
from collections import deque

def dfs(graph, node):
    stack = [node]
    visited[node] = 1
    while stack:
        cur = stack.pop()
        for adj in graph[cur]:
            if visited[adj] == 0:
                stack.append(adj)
                visited[adj] = 1

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

graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

count = 0
visited = [0]*(n+1)
for key in graph:
    if visited[key] == 0:
        count += 1
        dfs(graph, key)

print(count)

 

 

코드_유니온 파인드

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

parent = [0]*(n+1)
for i in range(1, n+1):
    parent[i] = i

def getParent(parent, x):
    if parent[x] == x:
        return x
    return getParent(parent, parent[x])

def unionParent(parent, x, y):
    x = getParent(parent, x)
    y = getParent(parent, y)

    if x < y:
        parent[y] = x
    else:
        parent[x] = y
    
for _ in range(m):
    a, b = map(int, input().split())
    unionParent(parent, a, b)

result = []
for a in parent: 
    result.append(getParent(parent, a))
#print(result)

result = result[1:] 

print(len(set(result)))

 

 

 

DFS, BFS 문제를 잘 풀 수 있으면 다양한 유형의 문제에서 활용이 가능하니 많이 많이 연습하자.