ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘] BFS/DFS 문제 풀이 _ 파이썬
    Dev Log/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 문제를 잘 풀 수 있으면 다양한 유형의 문제에서 활용이 가능하니 많이 많이 연습하자.

    댓글 0

Designed by Tistory.