-
[알고리즘] BFS/DFS 문제 풀이 _ 파이썬💫 Computer Science/Computer Science 2020. 9. 10. 15:25
▒ 코딩테스트 공부 방법
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 문제를 잘 풀 수 있으면 다양한 유형의 문제에서 활용이 가능하니 많이 많이 연습하자.
'💫 Computer Science > Computer Science' 카테고리의 다른 글
[개발자 상식] 개발자가 되기 위한 첫 걸음을 떼어줄 책 (0) 2023.03.15 [알고리즘] 완전탐색 문제풀이 _ 파이썬 (0) 2020.10.06 [알고리즘] 순열, 조합, 그래프 표현 _ 파이썬 (2) 2020.09.03 [알고리즘] 탐색 BFS, DFS _ 백준 1260 파이썬 (0) 2020.05.08 [알고리즘] 그리디 알고리즘 _ 백준11047 파이썬 (0) 2020.04.27