[SW정글] week03 후기 + DFS, BFS, 위상정렬

한계를 경험하고 극복해라.

 - Youngji Jang                                                                  

 

재수시절, 선생님에게 "혁아, 너는 잠때문에 인생 망할 거같다."라는 말을 들은 적이 있다.

 

그 정도로 나는 잠이 많다.

 

그러나 정글에 와서 "한계를 경험하고 극복해라" 라는 Youngji Jang의 말씀을 듣고 잠을 줄이려고 노력중이다.

(오늘은 코피도 났ㄷr...)

 

 

 

실력이 느는 것이 체감이 들지는 않지만, 정글에 오기전에 백준 실버 4-5문제만 골라풀던 내가

이제는 골드문제도 두려워하지 않고 푸는 모습을 보고 뿌듯한 감정을 느낀다.

 

시간이 벌써 한달 가까이 됐다. 

 

취업하는 날도 얼마 남지 않았으리라 믿는다.

 

그러나 4개월 후면 모두 흩어진다는 것이 조~~~끔 아쉽다.

 

잡설은 그만하고 week3동안 문제를 풀면서 느낀 점을 적어보쟈

---

최근 내카라 기출(근 3년)

 

 

DFS/BFS 18%
문자열 16%
단순구현 16%
완전탐색 12%
해시 12%
DP 4%
재귀함수 3%
다익스트라 3%

 

 

 

라고 한다. DFS/BFS가 1등이다. 똑바로 알고 넘어가도록 하자.

 

 

DFS/BFS

 

DFS, BFS, 위상정렬문제는 정답 코드가 비슷하다고 많이 느꼈다.

 

그래서, 기본적인 코드를 스니펫을 활용할 생각이다.

 

DFS - Depth First Search 깊이 우선 탐색

 

BFS - Breadth First Search 너비 우선 탐색

 

이름에서도 알 수 있듯이 dfs는 깊게 파고 드는 놈이고 bfs는 넓게 파고 드는 놈이다.

 

dfs는 스택 또는 재귀를 사용하고(나는 재귀를 쓸거다. 헷갈리지 않기 위해 그렇게 정했다.) bfs는 큐를 사용한다.

 

설명은 이 분이 기가막히게 잘설명하신다.

youtube.com/watch?v=_hxFgg7TLZQ&t=251s

 

예제 문제

 

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

1260번: DFS와 BFS

고고씽~

 

import sys
from collections import deque
sys.stdin = open("input.txt")
input = sys.stdin.readline


def dfs(n):
    print(n, end=' ')
    visited[n] = True
    for i in graph[n]:
        if not visited[i]:
            dfs(i)


def bfs(n):
    visited[n] = True
    queue = deque([n])
    while queue:
        v = queue.popleft()
        print(f"{v}", end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


N, M, V = map(int, input().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for lines in graph:
    lines.sort()

visited = [False]*(N+1)

dfs(V)

visited = [False] * (N+1)

print()
bfs(V)

 

 

이해했다면 위코드를 응용해서 dfs/bfs문제를 풀어보도록 하쟈

 

 

 

위상정렬 

 

위상정렬은 전제조건이 있다 바로 무방향, 순환하지 않는 그래프여야한다.

 

설명은 이분이 기가 막히게 하신다.

https://yoongrammer.tistory.com/86

위상 정렬(Topological sort) 개념 및 구현

 

문제

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

2252번: 줄 세우기

 

 

import sys
from collections import deque

sys.stdin = open("input.txt")

input = sys.stdin.readline

N, M = map(int, input().split())

graph = [[] for _ in range(N+1)]

# 진입차수
indegree = [0] * (N+1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    # 진입차수 count
    indegree[b] += 1


def topology():
    result = []
    q = deque()
    # 초기에 진입차수 0인 노드들 큐에 넣기
    for i in range(1, N+1):
        if indegree[i] == 0:
            q.append(i)

    # 큐가 빌때까지 반복
    while q:
        node = q.popleft()
        # 꺼낸 원소는 위상 정렬 결과값에 append
        result.append(node)
        # 꺼낸 노드랑 연결된 노드들 검색
        for next in graph[node]:
            indegree[next] -= 1
            # 새롭게 진입차수가 0이 된 노드들 큐에 넣기
            if indegree[next] == 0:
                q.append(next)
    for i in result:
        print(f"{i}", end=' ')


topology()

 

이번주도 열심히 해보자 ~