[11일차] TIL (DFS)

DFS

 

1. 전화번호 문자 조합

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

 

파이썬 답게 푼 풀이입니다. 짧게 쓸 수 있다는 장점이 있습니다.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone_map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }

        if digits == "":
            return []

        numbers = list(phone_map[digits[0]])
        # ['a', 'b', 'c']

        for digit in digits[1:]:
            # 다음과 같이 이중 for문을 한줄로 작성 가능하다.
            numbers = [old + new for old in numbers for new in list(phone_map[digit])]

        return numbers

다음은 재귀함수를 이용한 풀이입니다.

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index, path):
            # 끝까지 탐색하면 백트래킹
            if len(path) == len(digits):
                result.append(path)
                return

            # 입력값 자릿수 단위반복
            for i in range(index, len(digits)):
                # 숫자에 해당하는 모든 문자열 반복
                for j in dic[digits[i]]:
                    dfs(i + 1, path + j)

    if not digits:
        return []

    dic = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }

    result = []
    dfs(0, "")

    return result

 

 

2. 순열

https://leetcode.com/problems/permutations/

 

처음 문제를 보자마자 permutations로 풀면 짧게 풀 수 있겠다는 생각을 했습니다.

class Solution:
    from itertools import permutations
    def permute(self, nums: List[int]) -> List[List[int]]:
        return permutations(nums, len(nums))

하지만 DFS챕터이므로 DFS로 푸는 방법을 적어보겠습니다.(재귀)

 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        prev_elements = []

        def dfs(elements):
            # 리프 노드일때 결과 추가
            if len(elements) == 0:
                results.append(prev_elements[:])

            # 순열 생성 재귀 호출
            for e in elements:
                next_elements = elements[:] # 참조가 아닌 값을 복사한 리스트
                next_elements.remove(e) # 리스트에서 하나씩 빼주면서 순서를 바꾼 리스트 만들기

                prev_elements.append(e)
                dfs(next_elements)
                prev_elements.pop() # 다음 차례를 위해 값을 빼준다

        dfs(nums)
        return results

다음은 백트래킹시 유용하게 쓰일 템플릿을 첨부하겠습니다.

def dfs(node, state):
    if state is a solution:
        report(state) # e.g. add state to final result list
        return

    for child in children:
        if child is a part of a potential solution:
            state.add(child) # make move
            dfs(child, state)
            state.remove(child) # backtrack

 

3. 조합

https://leetcode.com/problems/combinations/

위 순열 문제와 마찬가지로 itertools의 combinations를 쓰면 2줄에 풀 수 있었습니다.

 

class Solution:
    from itertools import combinations
    
    def combine(self, n: int, k: int) -> List[List[int]]:
        lst = [i for i in range(1, n + 1)]
        return combinations(lst, k)

 

다음은 DFS를 이용해서 푼 문제입니다.(재귀)

 

 

4. 단지번호 붙이기

https://www.acmicpc.net/problem/2667

 

처음 스택을 이용한 방법이 떠올라 풀어보고자 했는데 실패하였습니다.

다음은 실패한 코드입니다.

n = int(input())

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

# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

print(graph)

danji_list = []
stack = []
danji_cnt = 0
for row in range(n):
    for col in range(n):
        if graph[row][col] != '1':
            continue

        danji_cnt += 1
        danji_result = 0
        stack = [(row, col)]
        while stack:
            x, y = stack.pop()
            graph[x][y] = '0'
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= n or graph[nx][ny] == '0':
                    continue
                stack.append((nx, ny))
                danji_result += 1
        danji_list.append(danji_result)

print(danji_cnt) # 단지 수
for cnt in danji_list:
    print(cnt)

 

다음은 재귀함수를 이용한 풀이입니다.

 

n = int(input())
graph = []
num = []

for i in range(n):
    graph.append(list(map(int, input())))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

print(graph)

def DFS(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    if graph[x][y] == 1:
        global count
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            DFS(nx, ny)
        return True
    return False


count = 0
result = 0

for i in range(n):
    for j in range(n):
        if DFS(i, j) == True:
            num.append(count)
            result += 1
            count = 0

num.sort()
print(result)
for i in range(len(num)):
    print(num[i])

 

5. 바이러스

https://www.acmicpc.net/problem/2606

 

BFS로 풀어본 풀이입니다.

n = int(input())
m = int(input())

from collections import deque

graph =[[] * i for i in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

count = 0
visited = [False] * (n + 1)

q = deque([1])

while q:
    node = q.popleft()
    visited[node] = True
    for i in graph[node]:
        if visited[i] == False:
            q.append(i)

# print(visited)

print(sum(visited) - 1)

 

추가로 DFS로도 풀어보았습니다.

위의 BFS도 마찬가지지만 True, False 를 1과 0으로 계산하여 sum 메소드를 사용할 수 있다는 것을 알 수 있습니다.

n = int(input())
m = int(input())

from collections import deque

graph =[[] * i for i in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (n + 1)

def dfs(graph, node, visited):
    visited[node] = True
    for i in graph[node]:
        if not visited[i]:
            dfs(graph, i, visited)

    return

dfs(graph, 1, visited)
print(sum(visited) - 1)