[백준 / BOJ] 6146 신아를 만나러

문제

출처 : www.acmicpc.net/problem/6146

6146번: 신아를 만나러

키파는 신아에게 가야한다. 

키파와 신아 사이에는 웅덩이가있고, 키파는 웅덩이를 피해서 가야한다.(키파가 신아에게 못가는경우는없다.)

키파의 위치는 항상 (0,0이고) 신아는 (-500~500, -500~500) 사이에 있다

키파는 상하좌우로만 움직일수있다.

풀이

BFS로 풀리는 문제였다.

 

-500~500까지 가능하므로 전체 칸의 갯수는 1000 * 1000 = 1000000개 이다.

중복으로 탐색하는 경우를 없애주면 최대 1000000번에 탐색이 끝난다. 

 

min_cnt변수를 선언하고 20억으로 초기화해준다.(최솟값을 저장할거임)

check[][]변수를 만들어서 해당위치에 도달했을때까지 이동거리가 check[][]에 저장된 이동거리보다 크다면, continue해주고 아니라면 check배열을 업데이트해준다

 

목적지에 최소시간으로 도달하는?? 알고리즘이 BFS지만 웅덩이가 있어서 예외가 있을수있으므로 목적지를 찾았다고 종료해주지않고 계속 탐색해준다.

웅덩이를 만났다면, 

min_cnt = min(min_cnt, now_cnt)로 min_cnt를 업데이트해준다.

 

탐색을하다 now_cnt값이 min_cnt보다 크거나 같아지면 탐색을 종료해준다.(무조건 최소시간보다 커짐)

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/6146%20%EC%8B%A0%EC%95%84%EB%A5%BC%20%EB%A7%8C%EB%82%98%EB%9F%AC/main.cpp

devxb/JJUNalgo