탐색 (Search) - DFS / BFS

먼저, 탐색을 하기 위해서는 지도(Graph)가 필요하다.

 

1. 그래프(Graph)란?

• 점(Node / Vertex): 도시, 사람, 데이터.
• 선(Edge): 도로, 친구 관계, 연결 선.

컴퓨터에게 이 지도를 알려주는 방법은 딱 2가지가 존재한다. 코딩테스트에 있어서는 2번(리스트) 방식을 많이 사용한다.

 

1.1. 2차원 배열(Adjacency Matrix)

• 방식: 엑셀 표처럼 모든 연결 관계를 1(연결됨)과 0(안됨)으로 표시하는 방법.
• 장점: graph[1][2]가 연결됐는지에 대한 확인이 빠르다.
• 단점: 점이 10,000개라면 표가 너무 커져서 메모리가 터진다.

 

1.2. 연결 리스트(Adjacency List)

• 방식: 각 점마다 자신과 연결된 애들만 나열한다.
• 장점: 필요한 것만 저장해서 메모리를 절약할 수 있다.

List<ArrayList> graph = new ArrayList<ArrayList<Integer>>;

 

 

---

 

2. DFS (깊이 우선 탐색) : 불도저

"한 우물만 판다."

갈림길이 나오면 무조건 한쪽으로 끝까지 들어간다. 막다른 골목에 다다르면 그제서야 뒤로 돌아 나와 다른 길을 찾는 탐색 방법이다.

• 핵심 도구: 재귀 함수(Recursion) 또는 스택(Stack)
• 순서: 1 → 2 → 4 → 5 (끝 찍고) → 3 ...

 

 

3. BFS (너비 우선 탐색) : 와이파이

주변부터 챙긴다.

나랑 가까운 곳부터 다 방문하고, 그 다음에 가까운곳을 방문한다. 와이파이 신호가 퍼지듯이 층층이 퍼져나가는 형태다.

• 핵심 도구: 큐(Queue). 줄세우기
• 순서: 1 → 2 → 3 (주변 다 확인 후) → 4 → 5 ...

 

 

BFS(너비우선 탐색)와 DFS(깊이우선 탐색)의 구조