탐색 알고리즘

탐색 알고리즘

12 Nov 2020

algorithm

2차원 지도 탐색

백준 2178 미로 탐색 문제

미로의 각 칸이 탐색 대상 노드이기 때문에 BFS로 풀어야 한다.

구현1
Location 객체를 HashSet에 보관하려면 hashCode, equals 메소드를 재정의해야 한다.
구현2
Node 객체를 만들어 Queue에 저장하며 조건에 맞는지 검사
구현3
모든 칸을 Node로 생성하여 Queue에 저장하지 않고 탐색해야 하는 칸만 Node 객체로 생성

최장거리를 구현해보자.

구현4

촤장거리 탐색도 BFS로 구현해야 한다.

목적지에 도착하자마자 distance를 리턴하는게 아니다. 도착하자마자 리턴하면 최단 거리가 된다.
마지막 distance 값이 최대거리이기 때문에 queue가 empty가 될 때까지 탐색을 계속한 후
max 값을 리턴해야 한다.

반복문으로 DFS 구현

구현5

반복문으로 깊이 우선 탐색을 구현하라.
last in, first out => BFS
last in, last out => DFS
깊이 우선 탐색의 리턴값 distance는 최단거리가 아니다.

비숫한 문제 : 프로그래머스 카카오프렌즈 컬러링북

BFS 구현 코드

스크린샷 2020-11-11 오후 2 01 01

입력 예제를 직접 그려보면 영역은 이렇게 나타난다.

백준 문제를 풀고 이 문제를 풀어보니 쉽게 이해할 수 있었다.
목적지 없이 전부 탐색해야 한다는 점과 색이 같으면 Node를 생성해 Queue에 넣어준다는 점만 다르고 풀이 방식은 똑같다.

풀어볼 문제 목록