BOJ 1260, 1920, 11724, 2343

1260 DFS와 BFS
1920 수 찾기
11724 연결 요소의 개수
2343 기타 레슨

---

1260 DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
 
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
 
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

---

DFS(Depth First Search) : Source node 에서 멀어지는 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 "가장 가까운 갈림길로 돌아와서(backtracking, 최근에 처리한 --> stack이 적합)" 그곳으로부터 미탐색한 다른 방향으로 재진행
BFS(Breath First Search) : Source node로 부터 가까운 노드들을 먼저 방문함. (가까운 노드들이 먼저 방문되고 그 노드들의 인접노드가 멀리 있는 노드들의 인접노드 보다 먼저 방문되야함. 즉 먼저(first) 처리(in)된 것 부터(first) 꺼내서(out) 처리해야하므로 queue가 적합); 트리 자료구조에서 root를 source node로 한 Level-order traversal과 유사함.

---

#include <stdio.h>
#include <stdbool.h>
#pragma warning(disable:4996)

int visited[1001] = { 0, }; // 방문 표시 초기화 (false)
int graph[1001][1001] = { 0, }; // 그래프 초기화 (false)
int queue[1001]; 

void dfs(int v,int n) { // 깊이 우선 탐색
	visited[v] = true; //이제 방문했기 때문에 true로 바꾼다. (더이상 0이 아님)
	printf("%d ", v);
	for (int i = 1; i <= n; i++) {
		if (graph[v][i] && !visited[i]) // 그래프에 방문하지 않았고 간선 존재
			dfs(i, n);
	}
}

void bfs(int v, int n) { // 너비 우선 탐색
	/* 큐 변수 선언 */
	int front = 0;
	int rear = 1;
	int pop;

	visited[v] = true;
	printf("%d ", v);
	queue[0] = v;
	while (front < rear) { // 큐가 비어있으면 반복 종료 
		pop = queue[front++]; // dequeue 연산 (맨 앞, 가장 먼저 들어온 값을 출력한다.)
		for (int i = 1; i <= n; i++){
			if (graph[pop][i] && !visited[i]) {
				visited[i] = true;
				printf("%d ", i);
				queue[rear++] = i; // enqueue 연산
			}
		}
	}
}

int main() {
	int n,m, v;

	scanf("%d%d%d", &n, &m, &v);

	//그래프 생성
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		graph[x][y] = 1; // 양방향 그래프
		graph[y][x] = 1;
	}
    
	//깊이 우선 탐색
	visited[v] = true;
	dfs(v,n);
	//--------------------------------------------------
	for (int i = 1; i <= n; i++) // 방문 노드 초기화
			visited[i] = false;
    //깊이 우선 탐색        
	visited[v] = true;
	printf("\n");
	bfs(v, n);
	return 0;
}

import sys
from collections import deque
input = sys.stdin.readline

# dfs 함수 정의(재귀)
def dfs(graph, v, visited):
    visited[v] = True # 방문 처리
    print(v, end=' ') # 현재 노드 출력
    for i in sorted(graph[v]): # 오름차순으로 이웃한 노드
        if not visited[i]: # 아직 방문하지 않은 노드가 있다면 방문
            dfs(graph, i, visited)

# bfs 함수 정의
def bfs(graph, start, visited):
    queue = deque([start]) # 큐에 현재 노드 삽입
    visited[start] = True # 방문 처리
    while queue: # 큐가 빌때 동안
        v = queue.popleft()
        print(v, end=' ') # 현재 노드 출력
        for i in sorted(graph[v]): # 오름차순으로 이웃한 노드
            if not visited[i]: # 아직 방문하지 않았다면
                queue.append(i) # 큐에 삽입
                visited[i] = True # 방문처리

n, m, start = map(int, input().rstrip().split()) # 정점, 간선, 시작정점

graph = [[] for j in range(n+1)] # 그려질 그래프 초기화
for k in range(m):
    a, b = map(int, input().rstrip().split()) # 이웃한 정점 연결시킴
    graph[a].append(b)
    graph[b].append(a)


visited = [False] * (n+1)
# dfs 함수 실행
dfs(graph, start, visited)

print()

visited = [False] * (n+1)
# bfs 함수 실행
bfs(graph, start, visited)

from collections import deque

# DFS 함수 정의, 깊이 우선 탐색
def dfs(v, visited, graph):
    visited[v] = True
    print(v, end=' ')
    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs(neighbor, visited, graph)

# BFS 함수 정의, 너비 우선 탐색
def bfs(start, graph):
    visited = [False] * (len(graph))
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for neighbor in graph[v]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

# 입력 받기
N, M, V = map(int, input().split())  # 정점 수, 간선 수, 시작 정점
graph = [[] for _ in range(N + 1)]

# 간선 정보 입력 받기
for _ in range(M):
    u, v = map(int, input().split())
    #양방향 그래프이기 때문에
    graph[u].append(v)
    graph[v].append(u)

# 각 정점의 인접 리스트를 정렬
for edges in graph:
    edges.sort()

# DFS와 BFS 결과 출력
visited_dfs = [False] * (N + 1)
dfs(V, visited_dfs, graph)
print()  # 줄바꿈
bfs(V, graph)

[백준] 1260번: DFS와 BFS - 파이썬

---

1920 수 찾기

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
 
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
 
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

---

[순차 탐색은 시간초과가 나온다.]

# 순차 탐색으로 구현
def sequential_search(n, target, array):
    # 각 원소를 하나씩 확인하며
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target:
            return 1 # 찾으면 1 반환
    return 0 #찾지 못하면 0 반환
#N
N = int(input())
# 생성된 리스트
array = list(map(int, input().split()))
# 배열 길이가 N과 일치하는지 확인
if len(array) != N:
    raise ValueError(f"Expected {N} elements for the main array, but got {len(array)} elements.")

#M
M = int(input())
# 확인할 리스트
checkArray = list(map(int, input().split()))
# 배열 길이가 M과 일치하는지 확인
if len(checkArray) != M:
    raise ValueError(f"Expected {M} elements for the check array, but got {len(checkArray)} elements.")

# checkArray의 각 요소에 대해 sequential_search 실행
for target in checkArray:
    print(sequential_search(N, target, array))

 
[이진탐색으로 해야 시간초과가 나오지 않는다.]

def binary_search(target, array):
    low, high = 0, len(array) - 1
    while low <= high:  # 검색해야 할 레코드가 있는 경우
        middle = (low + high) // 2  # middle 계산
        if target == array[middle]:  # 탐색 성공
            return 1  # 1 출력
        elif target < array[middle]:  # 왼쪽 부분 리스트 탐색
            high = middle - 1
        else:  # 오른쪽 부분 리스트 탐색
            low = middle + 1
    return 0  # 탐색 실패 -> 0 출력

# N 입력 및 배열 생성
N = int(input())
array = list(map(int, input().split()))
array.sort()  # 이진 탐색을 위해 배열을 정렬

# M 입력 및 확인할 리스트 생성
M = int(input())
checkArray = list(map(int, input().split()))

# checkArray의 각 요소에 대해 이진 탐색 실행
for target in checkArray:
    print(binary_search(target, array))