알고리즘 day 6 & 7

오늘은 이틀에 걸쳐 dfs,bfs를 배웠기에 한꺼번에 정리 하기로 한다.

 

dFS

DFS는 Depth First Search로 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조다.

- 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.

- 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.

- 위 과정을 반복한다.

 

DFS

 

BFS

우선 DFS 와 BFS 의 차이점을 살펴보자 DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다.

이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색하면 된다. → 그래서 스택을 사용!

BFS 는 현재 인접한 노드 먼저 방문해야 한다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. → 큐를 이용하면 BFS 를 구현할 수 있다. 

1. 루트 노드를 큐에 넣습니다.

2. 현재 큐의 노드를 빼서 visited 에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

4. 2부터 반복한다.

5. 큐가 비면 탐색을 종료한다.

 

BFS

 

이제 문제를 살펴보자

먼저 6일차의 문제들이다.

 

1.전화번호 문자 조합 https://leetcode.com/problems/letter-combinations-of-a-phone-number

LeetCode - The World's Leading Online Programming Learning Platform

from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        phone = {
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z']
        }

        def backtrack(index, path):
            if index == len(digits):
                result.append("".join(path))
                return
            for letter in phone[digits[index]]:
                backtrack(index + 1, path + [letter])

        result = []
        backtrack(0, [])
        return result

sol = Solution()
print(sol.letterCombinations("23"))  # ["ad","ae","af","bd","be","bf","cd","ce","cf"]
print(sol.letterCombinations(""))    # []
print(sol.letterCombinations("2"))    # ["a","b","c"]

 

이 문제는 재귀함수로 해결했다. 오늘 푼 문제들 대부분은 재귀함수로 했기에 필요한 경우만 코멘트를 남긴다.

 

2. 순열 https://leetcode.com/problems/permutations

LeetCode - The World's Leading Online Programming Learning Platform

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        n = len(nums)
      
        def backtrack(perm):
            if len(perm) == n:
                result.append(perm)
                return
            for num in nums:
                if num not in perm:
                    backtrack(perm + [num])

        backtrack([])
        return result

nums1 = [1, 2, 3]
nums2 = [0, 1]
nums3 = [1]

sol = Solution()

print(sol.permute(nums1))  # [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
print(sol.permute(nums2))  # [[0, 1], [1, 0]]
print(sol.permute(nums3))  # [[1]]


#다른 방법
from itertools import permutations
from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # itertools 모듈의 permutations 함수를 사용하여 모든 순열을 생성
        return list(permutations(nums))

 

 

3. 조합 https://leetcode.com/problems/combinations

LeetCode - The World's Leading Online Programming Learning Platform

from typing import List
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(start, path):
            if len(path) == k:
                result.append(path)

            for i in range(start, n+1):
                if i not in path:
                    backtrack(i+1, path+[i])

        result = []
        backtrack(1,[])
        return result

 

여기까지 똑같은 방식으로 해결했다. 남은 2문제는 좀 어려웠다.

 

 

4. 단지번호붙이기 https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

def dfs(grid, i, j):
    if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
        return 0
    
    grid[i][j] = '0'  
    
    count = 1 
    
    count += dfs(grid, i + 1, j)
    count += dfs(grid, i - 1, j)
    count += dfs(grid, i, j + 1)
    count += dfs(grid, i, j - 1)
    
    return count

def count_complexes(grid):
    if not grid:
        return 0
    
    complexes = []
    
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                count = dfs(grid, i, j)
                complexes.append(count)
                
    return complexes

N = int(input())
grid = [list(input()) for _ in range(N)]

complexes = count_complexes(grid)

print(len(complexes))
for count in sorted(complexes):
    print(count)

 

이건 dfs로 해결했다. xy로 계산하는게 좀 헷갈려서 count변수를 활용해서 재귀함수로 돌면서 기준의 사방에 있는 집들을 확인해줬다.

 

 

5. 바이러스 https://www.acmicpc.net/problem/2606

2606번: 바이러스

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

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

graph = [[] for _ 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)

dfs(graph, 1, visited)

count = sum(visited) - 1

print(count)

* 강의 참조
https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EB%AC%B8%EA%B3%BC%EC%83%9D%EB%8F%84-%EC%9D%B4%ED%95%B4%ED%95%98%EB%8A%94-dfs-%EC%9E%85%EB%AC%B8?inst=0938dd1f&utm_source=instructor&utm_medium=referral&utm_campaign=inflearn_%ED%8A%B8%EB%9E%98%ED%94%BD_promotion-link

 

dfs로 해결한 문제이고 문제를 거꾸로 풀어서 처음에 dfs,bfs에 대한 이해도가 낮아 참조 강의를 보면서 풀었다. 

 

 

이제 7일차의 문제들이다.

 

1. 부분 집합 https://leetcode.com/problems/subsets/

LeetCode - The World's Leading Online Programming Learning Platform

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start, path):
            result.append(path[:])
            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()

        result = []
        backtrack(0, [])
        return result

# 예시
nums1 = [1, 2, 3]
solution = Solution()
print(solution.subsets(nums1))  # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

nums2 = [0]
print(solution.subsets(nums2))  # [[], [0]]

 

이것도 재귀함수를 이용해서 nums의 범위를 넘으면 pop해주는 식으로 해결했다. 처음엔 중복을 고려해 set()을 사용할까했는데 재귀함수의 특성상 그럴 필요가 없다는 점을 배웠다.

 

 

2. 코스 스케줄 https://leetcode.com/problems/course-schedule

LeetCode - The World's Leading Online Programming Learning Platform

class Solution:
    def canFinish(self, numCourses, prerequisites):
        # 그래프의 인접 리스트 표현을 만듭니다.
        graph = [[0] * numCourses for _ in range(numCourses)]

        # 선행 과목 그래프를 구성합니다.
        for course, pre_course in prerequisites:
            graph[course][pre_course] = 1

        # 위상 정렬을 위한 진입 차수 배열을 초기화합니다.
        in_degree = [0] * numCourses
        for i in range(numCourses):
            for j in range(numCourses):
                in_degree[i] += graph[j][i]

        # 위상 정렬을 수행합니다.
        count = 0
        queue = []
        for i in range(numCourses):
            if in_degree[i] == 0:
                queue.append(i)

        while queue:
            course = queue.pop(0)
            count += 1
            for i in range(numCourses):
                if graph[course][i]:
                    in_degree[i] -= 1
                    if in_degree[i] == 0:
                        queue.append(i)

        return count == numCourses

# 테스트 케이스
solution = Solution()
print(solution.canFinish(2, [[1,0]])) # 출력: True
print(solution.canFinish(2, [[1,0],[0,1]])) # 출력: False

 

오늘 문제 중 가장 어려웠다. 처음엔 dfs를 고려했고 여의치 않아 연결리스트로 풀어볼까도 했는데 생각만큼 잘 되지 않았다. 그래서 구글링은 하니 위상 정렬이란게 있었다. 인접행렬은 순회하면서 진입차수(간선)를 계산해주고 진입차수가 0인 과목들을 큐에 추가 한 뒤 하나씩 꺼내면서 count를 증가해주고 이 과목과 연결된 과목들의 진입차수를 감소하는걸 큐가 빌때까지 반복해준 뒤 count와 전체 과목의 수를 비교해서 같으며 true 다르면 false를 반환하는 방식으로 해결했다. 

위상정렬을 처음 접하기도 했고 그래프를 직접 그려가면서 했는데도 문제 자체가 어려웠다.

 

*위상정렬
위상 정렬은 방향 그래프에서 노드들을 순서대로 나열하는 알고리즘. dfs나 bfs가 특정 노드를 찾는데 사용되는 반면에 이건 노드들 간의 선후 관계를 찾는데 사용된다.

 

 

3. DFS와 BFS https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def dfs(self, start):
        visited = set()
        stack = [start]

        while stack:
            node = stack.pop()
            if node not in visited:
                print(node, end=' ')
                visited.add(node)
                stack.extend(sorted(self.graph[node], reverse=True))

    def bfs(self, start):
        visited = set()
        queue = deque([start])

        while queue:
            node = queue.popleft()
            if node not in visited:
                print(node, end=' ')
                visited.add(node)
                queue.extend(sorted(self.graph[node]))

N, M, V = 4, 5, 1
graph = Graph()

edges = [(1, 2), (1, 3), (1, 4), (2, 4), (3, 4)]
for u, v in edges:
    graph.add_edge(u, v)

print("DFS:", end=' ')
graph.dfs(V)
print()

print("BFS:", end=' ')
graph.bfs(V)

 

dfs는 시작 노드를 스택에 넣고, 스택이 빌 때까지 반복하면서 노드를 꺼내고 방문 여부를 확인한다. 방문하지 않은 노드라면 출력하고 방문한 노드로 표시한 후, 해당 노드와 연결된 인접 노드들을 스택에 추가한다. dfs는 스택을 이용하니까 스택은 후입선출방식이라서 리버스로 역순으로 정렬한뒤 스택에 extend 했다. bfs도 같은 방식이나 차이점은 큐는 선입선출 방식이니까 리버스를 해주지 않았다.

 

 

1, 2, 3 더하기 https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

def count_ways(n):
    dp = [0] * (n + 1)
    dp[0] = 1 .

    for i in range(1, n + 1):
        if i >= 1:
            dp[i] += dp[i - 1]  
        if i >= 2:
            dp[i] += dp[i - 2] 
        if i >= 3:
            dp[i] += dp[i - 3] 

    return dp[n]
print(count_ways(4))

 

이 문제는 문제자체는 이해하기 쉬웠는데 어떤 식으로 접근해야 할지 막막했다. 그래서 또 구글링을 하니 점화식이란게 있었다. 이 문제에서 ways(n)=ways(n−1)+ways(n−2)+ways(n−3)의 점화식을 이용해서 해결했다.

 

 

5. 암호 만들기 https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

from itertools import combinations


def find_possible_passwords(L, letters):
    vowels = {'a', 'e', 'i', 'o', 'u'}
    passwords = set()

    for comb in combinations(letters, L):
        num_vowels = sum(1 for char in comb if char in vowels)
        num_consonants = L - num_vowels

        if num_vowels >= 1 and num_consonants >= 2:
            passwords.add(''.join(sorted(comb)))

    return passwords



L, C = map(int, input().split())
letters = input().split()

possible_passwords = find_possible_passwords(L, letters)


for password in sorted(possible_passwords):
    print(password)

 

이문제는 문제가 어렵다기 보다는 dfs나 bfs를 어떻게 적용할까에 대한 고민이 길었다. 도저히 생각이 안나 콤비네이션 내장함수를 이용해서 그냥 풀었는데 다행이 통과했다. 코드리뷰할때 매니저님이 코드를 보여주셨는데 저 점화식을 재귀함수로 푼것이었다. 

 

* 추가 공부

재귀함수에 대한 공부가 더 필요하다. 할때마다 헷갈린다. 

1. 하노이의 탑

2. 피보나치 수열

3. https://www.acmicpc.net/problem/1074(매니저님 추천 문제)