5/2 스터디 문제

1번 문제.
https://www.acmicpc.net/problem/1260
-> DFS와 BFS

그림을 통해서 어떤 모양인지 확인한다.

----------------- 예제 1 fig ------------------------------------- 예제 2 fig ----------------

1번 문제 풀이 코드

import sys
from collections import deque

# dfs 함수
def dfs(v):
    # 방문한 곳에 1을 삽입
    visited1[v] = 1
    print(v, end=' ')
    # 재귀 함수 선언
    for i in range(1, n + 1):
        if visited1[i] == 0 and matrix[v][i] == 1:
            dfs(i)

# bfs 함수
def bfs(v):
    # 방문할 곳을 넣을 덱
    deq = deque()
    deq.append(v)
    # 방문한 곳에 1을 삽입
    visited2[v] = 1
    # 덱 안에 데이터가 없어질때까지 반복문 실행
    while deq:
        v = deq.popleft()
        print(v, end=' ')
        for i in range(1, n + 1):
            if visited2[i] == 0 and matrix[v][i] == 1:
                deq.append(i)
                visited2[i] = 1

# n: 정점 갯수, m: 간선 갯수, v: 탐색을 시작할 정점 번호 입력 받기
n, m, v = map(int, sys.stdin.readline().rstrip().split())

# 배열은 0부터 시작하므로 n개의 수에 1을 더해 값들의 위치를 입력 받은 그대로 생각한다.
# n개의 숫자들 사이의 인접하는 0행렬을 생성
matrix = [[0] * (n + 1) for _ in range(n + 1)]
# 방문한 곳 확인을 위한 배열 생성
visited1 = [0] * (n + 1)
visited2 = [0] * (n + 1)

# 간선 갯수에 맞춰 두 개의 숫자들 입력 받기
for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    # 입력 받은 두 값의 위치 체크를 위해 위치에 맞게 1 삽입
    matrix[a][b] = matrix[b][a] = 1

dfs(v)
print()
bfs(v)

=======================================================
아직 많이 부족하다... dfs bfs를 잘 모르기 때문에 아예 개념부터 다시 공부해야 했다.. 이 파트는 특히 많은 문제를 풀어봐야 할 필요가 있다.
오늘은 여기까지.