[3주차] Java 알고리즘 - DFS, BFS

BufferedReader

https://jhnyang.tistory.com/entry/Java-%EC%9E%90%EB%B0%94-%EC%9E%85%EC%B6%9C%EB%A0%A5-BufferedReaderBufferedWriter

counting sort

DFS, BFS

깊이우선

stack, 재귀로 구현

재귀: 다시 돌아가기 = 팩토리얼 (자기참고) - 스택오버플로 발생 가능
최대 깊이 가서 완전탐색

##기본 예제 백준 2602 바이러스 DFS 풀이 // 재귀함수를 이용한 DFS

import sys
N_computer=int(input())
visited=[False]*(N_computer+1)
N_E=int(input())
E=[[] for i in range(N_computer+1)]

for i in range(N_E):
    S,D = map(int, input().split())
    E[S].append(D)
    E[D].append(S)
count=0

##dfs풀이
def dfs(E, v, visited):
    visited[v]=True    #시작노드 방문처리
    global count
    for i in E[v]:         #시작노드와 인접한노드 순차적 탐색
        if not visited[i]:
            count+=1
            dfs(E, i, visited)
dfs(E, 1, visited)
print(count)

병합정렬 2751,1517

기수정렬 10989

깊이우선탐색

11724

2023

약수의 성질을 생각해보면 제곱근을 기준으로 대칭이 된다. 여기서 소수가 될 수 있는 수는 제곱근 이하가 된다

13023

문제
https://www.acmicpc.net/problem/13023

풀이
https://hanyeop.tistory.com/419

너비우선탐색

재귀 안 됨.. FIFO라서

DFS는 Stack(FILO)으로, BFS는 Queue(FIFO)를 이용해서 구현했는데요.
저는 동일하게 BFS는 Queue를 이용해서 구현했지만,
DFS는 Stack을 사용하지 않고, 재귀를 통해 구현했습니다!

무방향-양쪽

1260

2178 미로 찾기

https://www.acmicpc.net/problem/2178
재귀로도 풀리나, 풀려면 재귀-1을 해줘야 함.
Recursive 로 구현
https://movahws.tistory.com/105

설명 : BFS -> Depth 도착 시 끝!

1167 트리의 지름

문제 : https://moonsbeen.tistory.com/101
해설 : (DFS)