심화 과정 7 일차

1. 자료구조 및 알고리즘 7일차 수강하기

 - BFS

 

 - 백트래킹

 

2. 새롭게 알게된 지식

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 - 접근 : 

 

 DFS 가 더욱 적합하지만 BFS 를 배웠기 때문에 BFS 로 풀기

 

 - 코드 구현 : 

 

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 - 접근 : 

 

 DFS 를 사용하여 탐색, 탐색이 끝나면 해당 시작점을 방문 노드에서 삭제

 

 - 코드 구현 : 

 

 

 

 

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

1260번: DFS와 BFS

 

 - 접근 : 

 

 DFS 와 BFS 로 같은 문제 풀어 보기

 

 - 코드 구현 : 

 

import sys
from collections import deque

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write
        self.dfs_visited = []
        self.bfs_visited = []
        self.dict = {}
    
    def dfs(self, start : int, res = '') -> str:
        res += str(start) + ' '
        self.dfs_visited[start] = True
            
        for next in self.dict[start]:
            if not self.dfs_visited[next]:
                res = self.dfs(next, res)

        return res

    def bfs(self, start : int) -> str:
        Q = deque()
        Q.append(start)
        res = str(start) + ' '
        self.bfs_visited[start] = True

        while Q :
            now = Q.popleft()
            for next in self.dict[now]:
                if not self.bfs_visited[next]:
                    res += str(next) + ' '
                    Q.append(next)
                    self.bfs_visited[next] = True

        return res
        
    def run(self):
        N, M, V = map(int, self.input().split(' '))
        self.dict = { i : [] for i in range(1, N+1)}
        self.dfs_visited = [False] * (N + 1)
        self.bfs_visited = [False] * (N + 1)
        
        for _ in range(M):
            a,b = map(int,self.input().split(' '))
            self.dict[a].append(b)
            self.dict[b].append(a)

        for values in self.dict.values():
            values.sort()

        self.output(self.dfs(V) + '\n')
        self.output(self.bfs(V) + '\n')

s = Solution()
s.run()

 

 

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

9095번: 1, 2, 3 더하기

 

 - 접근 : 

 

 DFS 로 접근 하였지만, 실제 해결방법은 DP를 사용해야 함

 

 - 코드 구현 : 

 

 

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

1759번: 암호 만들기

 

 - 접근 : 

 

 브루트 포스로 해당하는 모든 경우의 수를 찾음

 

 - 코드 구현 :