DFS/BFS

1.概要

Stackとは?

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.pop()

print(stack[::-1]) #최상단 원소부터 출력
print(stack) #최하단 원소부터 출력

#include<bits/stdc++.h>

using namespace std;

stack<int> s;

int main(void) {
	s.push(5);
    s.push(2);
    s.push(3);
    s,pop();
    
    while(!s.empty()){
    	cout<<s.top()<<' ';
        s.pop();
    }
}

3.キュー資料構造とは?

from collections import deque

#큐 구현을 위해 deque 라이브러리 사용
queue = deque()

queue.append(5)
queue.append(2)
queue.popleft()

print(queue) #먼저 들어온 순서대로 출력
queue.reverse() #역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

#include<bits/stdc++.h>

using namespace std;

queue<int> q;

int main(void) {
	q.push(5);
    q.push(2);
    q.pop();
    q.push(1);
    while(!q.empty()){
    	cout<<q.front()<<' ';
        q.pop();
    }
}

4.再帰関数

def recursive_function(i):
	#100번째 호출 종료
    if i==100:
    	return;
    print(i,'번째 재귀함수에서', i+1,'번째 재귀함수 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)

#반복적으로 구현한 n!
def factorial_iterative(n):
	result = 1
    #1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1):
    	result *=i
    return result
#재귀적으로 구현한 n!
def factorial_recursive(n):
	if n <=1:
    	return 
    #n! n * (n-1)!그대로 코드로 작성
    return n*factorial_recursive(n-1)

def gcd(a,b):
	if a % b ==0:
    	return b
    else : 
    	return gcd(b, a%b)
print(gcd(192,162))

5. DFS(Depth-First Search)

#DFS 메서드 정의
def dfs(graph, v, visited):
	#현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ') # 해당 노드의 인덱스 번호 출력
    #현재 노드와 연결된 다른 노드 재귀적 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

grah = [
		[],
        [2,3,8],
        [1,7],
        [1,4,5],
        [3,5],
        [3,4],
        [7],
        [2,6,8],
        [1,7],
]
#각 노드가 방문된 정보를 표현(1차원 리스트)
#우리가 1번 인덱스부터 사용하기 때문에 하나 더 큰 크기로 1차원 리스트 초기화
visited = [False] *9 

#정의된 dfs 함수 호출
dfs(graph, 1, visited)

#include<bits/stdc++.h>
using namespace std;

bool visited[9];
vector<int> graph[9]; #얘도 1부터 보기 위해 9

void dfs(int x){
	visited[x] = true;
    cout<<x<<' ';
    for (int i =0; i<graph[x].size(); i++){
    	int y = graph[x][i];
        if (!visited[y]) dfs(y);
    }
}

6. BFS (Breadth-First Search)

from collections import deqqe

#BFS 메서드 정의
def bfs(graph, start, visited):
	#큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    #현재 노드를 방문 처리
    visited[start] = True
    #큐가 빌 때까지 반복
    while queue:
    	#큐에서 하나의 원소를 뽑아 출력
        v=queue.popleft()
        print(v, end=' ')
        #아직 방문하지 않은 원소 큐 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i]=True

graph=[
		[],
       [2,3,8],
       [1,7],
       [1,4,5],
       [3,5],
       [3,4],
       [7],
       [2,6,8],
       [1,7]
 ]
 #각 노드가 방문된 정보를 표현(1차원 리스트)
 visited = [False] * 9
 
 #정의된 BFS 함수 호출
 bfs(graph, 1, visited)

7.代表的な質問に答える

n,m=map(int, input().split())

#2차원 리스트의 맵 정보 받기
graph=[]
for i in range(n):
	graph.append(list(map(int,input())))
    
# DFS로 특정 노드를 방문하고 모든 노드 방문
def dfs(x,y):
	#주어진 범위를 벗어나면 즉시 종료
    if x<=-1 or x>=n or y<=-1 or y>=m:
    	return False
    #현재 노드를 아직 방문하지 않았다면
    if graph[x][y] ==0:
    	#해당 노드 방문 처리
        graph[x][y] =1
        # 상,하,좌,우 위치 모두 재귀적 호출
        dfs(x-1, y)
        dfs(x, y-1) # 다 방문처리 해줘! 
        dfs(x+1, y)
        dfs(x,y+1)
        return True #상하좌우는 true 리턴X
    return False

#모든 노드에 대하여 읍료수 채우기
result=0
for i in range(n):
	for j in range(m):
    	#현재 위치에서 DFS 수행
        if dfs(i,j) == True:
        	result +=1
print(result)

from collections import deque

#N,M을 공백을 기준으로 구분하여 입력 받기
n,m = map(int, input().split())
#2차원 리스트 만들기
graph=[]
for i in range(n):
	graph.append(list(map(int,input())))
    
#이동할 네 가지 방향 정의 (상,하,좌,우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

#BFS 소스코드 구현
def bfs(x,y):
	#큐 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x,y)) #튜플 담아!
    #큐가 빌 때까지 반복하기
    while queue:
    	x,y = queue.popleft()
        #현재 위치에서 4방향 위치 확인
        for i in range(4):
        nx = x + dx[i]
        ny = y+ dy[i]
        #미로 공간을 벗어난 경우 무시
        	if nx<0 or nx>=n or ny<0 or ny >=m:
        		continue
        #벽인 경우 무시
        	if graph[nx][ny] ==0:
        		continue
        #해당 노드를 처음 방문하는 경우만 최단 거리 기록
        if graph[nx][ny] ==1:
        	graph[nx][ny] = graph [x][y] +1
            queue.append((nx,ny))
       #가장 오른쪽 아래까지의 최단거리 반환
   return graph[n-1][m-1]
print(bfs(0,0))