코딩테스트

[코딩테스트]BFS

독학하는 정호빈 2022. 1. 1. 19:31

책 '이것이 취업을 위한 코딩 테스트다'를

기반으로 공부하였습니다.

https://github.com/ndb796/python-for-coding-test

 

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

[한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소

github.com

 

1. BFS(너비 우선 탐색)이란 그래프에서 가까운 인접노드부터 탐색하는 알고리즘 입니다.

 

2. BFS 작성코드 : 작은숫자 순으로 큐에 집어넣음

 

*우선순위에 따라 탐색이 달라질 수 있습니다.*

import java.util.*;

public class MyBFS {
	
	static LinkedList<Node> abc = new LinkedList<Node>();
	
    //Queue를 이용한 BFS구현
	public static void bfs(int num) {
		Queue<Node> a = new LinkedList<Node>();
		a.offer(abc.get(num));
		abc.get(num).visited=true;
		while(!a.isEmpty()) {
			int y=a.poll().var;
			System.out.print(y+" ");
			for(int i=0;i<abc.get(y).adjacent.size();i++) {
				if(!abc.get(y).adjacent.get(i).visited) {
					a.offer(abc.get(y).adjacent.get(i));
					abc.get(y).adjacent.get(i).visited = true;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		for(int i=0;i<9;i++) {
			abc.add(new Node(i));
		}
		abc.get(1).adjacent.add(abc.get(2));
		abc.get(1).adjacent.add(abc.get(3));
		abc.get(1).adjacent.add(abc.get(8));
		
		abc.get(2).adjacent.add(abc.get(1));
		abc.get(2).adjacent.add(abc.get(7));
		
		abc.get(3).adjacent.add(abc.get(1));
		abc.get(3).adjacent.add(abc.get(4));
		abc.get(3).adjacent.add(abc.get(5));
		
		abc.get(4).adjacent.add(abc.get(3));
		abc.get(4).adjacent.add(abc.get(5));
		
		abc.get(5).adjacent.add(abc.get(3));
		abc.get(5).adjacent.add(abc.get(4));
		
		abc.get(6).adjacent.add(abc.get(7));
		
		abc.get(7).adjacent.add(abc.get(2));
		abc.get(7).adjacent.add(abc.get(6));
		abc.get(7).adjacent.add(abc.get(8));
		
		abc.get(8).adjacent.add(abc.get(1));
		abc.get(8).adjacent.add(abc.get(7));
		
		bfs(1);
	}

}

 

 이번에는 BFS를 구현해보았습니다. DFS에서 끙끙 대며 책안보고 코딩한 보람이 있던건지 DFS에 비해 BFS는 코드 작성을 마칠 때까지 오류가 적었던 것 같습니다. Node는 이전 글에서 사용한 Node클래스를 사용하였고, 그래프 또한 동일합니다. DFS와 BFS의 예제를 구현하면서 생각한 것은 확실히 다른 알고리즘들 보다 깊게 생각해봐야겠다라고 봅니다. 

 

 책이랑 다른 참고 자료는 안보고 코드를 작성하려다 보니까 변수자체도 난해하고, 좀 지저분한 감이 있습니다 ㅎㅎ

 

 그래도 이렇게 안보고 한뒤에 예제의 풀이나 해설을 나만의 답과 비교하는 과정이 저는 정말 자신한테 도움이 된다고 생각하고있어서 항상 코딩을 할 땐 먼저 오답이라도 클론코딩을 거치지 않고 자신만의 생각으로 짜보는 편입니다.

 

 다들 화이팅입니다!