[IT/코딩테스트] 99클럽 코테 스터디6일차 TIL + BOJ1260

 

오늘의 문제

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

 

이번주의 주제는 DFS, BFS 였다. ( 두둥...!)

문제 읽고 파악할 필요없이 벌써 질문에 대놓고 써있기..

 

그리고 오늘은 나의 첫번째 풀이. 라고 하기에는 조금 그런것이..

코테 책과 강의, 다른 분들이 푸신 문제들을 보면서 공부를 한 후에 코드를 작성해보았다.

 

그래서 오늘은 나의 첫 풀이가 아닌, 핵심-배운 내용 느낌으로 정리하려고 한다.

내일 새로운 문제를 받으면, 그 문제를 혼자 풀어보고 정리를 할 것이다🤭🍀

---

오늘 공부한 내용

** 자료구조

 

- 스택(stack) : 선입후출 or 후입선출 👉 박스 쌓기

리스트 사용해서 구현

 

- 큐(queue) : 선입선출 👉 놀이공원 줄 

collection 모듈에서 제공하는 deque 자료구조 활용

 

- 재귀함수 : 자기 자신을 다시 호출하는 함수 

 

 

** 탐색 알고리즘

 

- 그래프 : 노드(정점), 간선

인접 행렬, 인접 리스트로 구현 가능

 

- DFS : 깊이우선탐색 👉 재귀함수로 구현

1. 현재 노드 방문처리 and 출력
<for> : 해당 노드 방문을 안 했는데, 연결된 다른 노드가 있다면
2. 현재 노드와 연결된 다른 노드들 방문
3. 재귀적으로 호출

 

- BFS : 너비우선탐색 👉 큐로 구현

1. 큐 정의 (시작 노드 넣어두기)
2. 현재 노드 방문처리
<while> : 큐가 빌 때까지
3. 큐에서 하나 뽑아서 출력
<for> : 해당 노드 방문을 안 했는데, 연결된 다른 노드가 있다면
4. 현재 노드와 연결된 다른 노드들 방문 and 큐에 삽입
5. 해당 노드 방문 처리

 

 

위의 내용 공부하면서 그림그려보고 손코딩 해보면서 계속 이해하느라 권장 시간도 넘기고

결국 한번 리셋하고 문제 풀기 시작했을 때 다시 켰다 ㅋㅋㅋ 😂😂😂

 

 

 

해결 코드

import sys
from collections import deque

n, m, v = map(int, sys.stdin.readline().split())

graph = [[False] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a][b] = True
    graph[b][a] = True

visited1 = [False] * (n+1)
visited2 = [False] * (n+1)


def dfs(v):
    visited1[v] = True # 방문처리
    print(v, end=' ')
    for i in range(1, n+1):
        # 해당 노드(i)를 방문하지 않았는데 v노드 와 연결이 되어있다면, i 노트 방문 - 깊이탐색
        if not visited1[i] and graph[v][i]:
            dfs(i)


def bfs(v):
    queue = deque([v])
    visited2[v] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in range(1, n+1):
            # 해당 노드(i)를 방문하지 않았는데 v노드 와 연결이 되어있다면, i 노트 방문 - 너비탐색
            if not visited2[i] and graph[v][i]:
                queue.append(i)
                visited2[i] = True


# dfs 수행 결과
dfs(v)
print()
# bfs 수행 결과
bfs(v)

 

 

정답

 

오늘은 dfs-bfs 따로 강의도 듣고 책보고 공부도 하고 정리하느라 시간을 많이 보냈다 🥹

역시,, 그래프 이론으로 들어오니까 내 머리가 느려지기 시작한다 ㅋㅋㅋ

 

그래도 저번주에 이진탐색, 투포인터에 대해서 살짝 감을 잡은 것처럼.

이번주는 dfs-bfs 를 점령해보자!!

 

화이팅!!

 

---

오늘 한 공부

1. 코테 1문제

2. DFS - BFS 강의 듣기

3. 강의 들은 내용 정리 - 깃헙 업로드

4. 대규모 시스템 설계 기초 : 4장 읽기

5. 영어 보카 DAY10 암기

6. TIL 적기

 

즐겨보자...