심화 과정 6 일차

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

 - DFS

 

 - 그래프

 

2. 새롭게 알게된 지식

 * Python 2차 배열을 초기화 관련

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 - 접근 : 

 

 

 - 코드 구현 : 

 

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 - 접근 : 

 

 

 - 코드 구현 : 

 

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 - 접근 : 

 

 

 - 코드 구현 : 

 

 

 

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

2667번: 단지번호붙이기

 

 - 접근 : 

 

 

 - 코드 구현 : 

 

import sys

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write
        self.input_data = []
        self.dir_list = [[1, 0],[0, 1],[-1, 0],[0, -1]]
        self.visited = []
        self.temp_res = 0
        self.n = 0

    #dfs
    def answer(self, x, y):
        
        self.temp_res += 1
        self.visited[x][y] = True

        for dir in self.dir_list:
            next_x = x + dir[0]
            next_y = y + dir[1]

            if next_x < 0 or next_y < 0 or next_x >= self.n or next_y >= self.n:
                continue

            if self.visited[next_x][next_y] or self.input_data[next_x][next_y] == '0':
                continue

            self.answer(next_x, next_y)


    def run(self):
        N = int(self.input().rstrip())
        input_data = []

        for _ in range(N):
            input_data.append(self.input().rstrip())

        self.input_data = input_data
        self.visited = [[False for _ in range(N)] for _ in range(N)]
        self.n = N
        res = []

        for i in range(N):
            for j in range(N):
                if not self.visited[i][j] and self.input_data[i][j] == '1':
                    self.temp_res = 0
                    self.answer(i,j)
                    res.append(self.temp_res)

        self.output(str(len(res)) + '\n')
        for n in sorted(res):
            self.output(str(n) + '\n')

s = Solution()
s.run()

 

 

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

2606번: 바이러스

 

 - 접근 : 

 

 

 

 

 - 코드 구현 : 

 

import sys

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write
        self.input_data = {}
        self.visited = []
        self.n = 0
        self.res = 0

    #dfs
    def answer(self, start):
        self.visited[start] = True

        for n in self.input_data[start]:
            if not self.visited[n]:
                self.res += 1
                self.answer(n)

    def run(self):
        N = int(self.input().rstrip())
        self.n = N

        for i in range(1, N+1):
            self.input_data[i] = []

        self.visited = [False] * (N+1)

        #양방향 그래프 설정
        for _ in range(int(self.input().rstrip())):
            a,b = map(int,self.input().split(' '))
            self.input_data[a].append(b)
            self.input_data[b].append(a)

        # 1번 PC 전파
        self.answer(1)
        self.output(str(self.res) + '\n')

s = Solution()
s.run()