DFS BFS

DFS depth first search

깊이 우선 탐색 : 깊은 부분을 우선적으로 탐색하는 알고리즘

1. 탐색시작노드(v)를 스택에 삽입 + 방문처리(visited[v]=true)
2. 최상단노드(v)에 방문하지 않는 인접노드(visited[w]=false 인 w)가 하나라도 있으면, 그 인접한 노드를 스택에 넣기(stack.add(w)) + 방문처리(visited[w]=true)
3. 최상단 노드 인접 노드 전부 방문했다면, 스택에서 최상단 노드 꺼내기(stack.pop())

BFS breath first search

너비 우선 탐색 : 가까운 노드부터 우선적으로 탐색하는 알고리즘

1. 탐색시작노드(v)를 큐에 삽입 + 방문처리(visited[v]=true)
2. 큐에서 노드 꺼내기(queue.poll())
3. 꺼낸 노드의 인접 노드 중 방문하지 않는 노드(w)를 모두 큐에 삽입(visited[w]=false , queue.add(w)) + 방문처리(visited[w]=true)

• dfs는 넣고 방문처리하고 노드 꺼내는데, bfs는 노드 꺼내고 넣고 방문처리

---

psuedo Code

DFS

DFS(v):
	n<- #node
	visited <- size=n, initialized to false//방문처리공간
	stack<-createStack();//dfs 구현을 위한 스택만들기
	
	push(stack, v);//시작노드 스택에 넣기
	visited[v]<-true;//현재 방문한 노드 방문처리
	
	while not isEmpty(stack) do//스택이 비어있지 않을때까지 반복
			v<-pop(stack)//스택에서 최상단노드 꺼내서
			visit(v)
		
			for each neighbor w of v do
				if visited[w]=false then //최상단 노드의 인접노드에 방문하지 않았다면
						push(stack, w)//스택에 인접노드 넣기
						visited[w]<-true

BFS

BFS(v):
    n <- number of nodes
    visited <- array of size n, initialized to false // 방문처리 공간
    queue <- createQueue() // BFS 구현을 위한 큐 만들기

    offer(queue, v) // 시작 노드 큐에 넣기
    visited[v] <- true // 현재 방문한 노드 방문처리

    while not isEmpty(queue) do // 큐가 비어있지 않을 때까지
        v <- poll(queue) // 큐에서 최상단 노드 꺼내서
        visit(v)

        for each neighbor w of v do
            if visited[w] = false then // 최상단 노드의 인접노드에 방문하지 않았다면
                offer(queue, w) // 큐에 인접노드 넣기
                visited[w] <- true // 방문처리

---

예시 : 미로 찾기

public class Main{
	static int n, m;
	static int[][]graph;
	static int[][]visited;
	static int[][]dx={0,0,-1,+1};
	static int[][]dy={-1, +1,0,0};

	//노드의 좌표를 할당하는 클래스 : Node
	static class Node{
		int x;
		int y;
		public Node(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}

public static void main(string[] args) throws IOException{
	BufferReader bf=new BufferReader(new InputStream(system.in));
	StringTokenizer st=new StringTokenizer(br.readLine());
	n=Integer.parseInt(st.nextToken());
	m=Integer.parseInt(st.nextToken());

	//그래프, 방문처리 공간 만들기
	graph=new int[n][m];
	visited=new boolean[n][m];

	//그래프 초기화
	for(int i=0;i<n;i++){
		st=new StringTokenizer(br.readLine());
		
		for(int j=0;j<m;j++){
			graph[i][j]=Integer.parseInt(st.nextToken());
		}
	}
	bfs(0,0);//시작 위치 넣어서 bfs실행
}

public static void bfs(int x, int y){
	Queue<Node> queue=new LinkedList<>();//bfs를 위한 큐
	queue.offer(Node(x, y));//시작 노드 큐에 넣기
	visited[x][y]=false;//시작 노드 방문 처리

	while(!queue.isEmpty()){//큐가 비기 전까지
		Node node=queue.poll();//큐에서 노드pop
		int cur_x=node.x;//꺼내온 노드를 현위치 x로 설정
		int cur_y=node.y;//꺼내온 노드를 현위치 y로 설정

		for(int i=0;i<4;i++){//상하좌우 확인
			int next_x=dx[i]+cur_x;//다음x위치
			int next_y=dy[i]+cur_y;//다음 y위치

			if(next_x<0 || next_y<0 || next_x>n || next_y>m) continue;//칸을 벗어나면 x
			if(visited[next_x][next_y]==0) continue;//이미 방문한곳 x
			if(graph[next_x][next_y]==0) continue;//장애물인곳 x
			else {
				queue.offer(Node(next_x, next_y));//큐에 다음위치 넣기
				visited[next_x][next_y]=true;//다음위치 방문처리
			}
}

[프로그래머스 | lv.2 | DFS / BFS] 타겟넘버

[프로그래머스 | lv2 | DFS/BFS] 게임 맵 최단거리