Hide and Seek

최근에 풀었던 대표적인 BFS 문제인 토마토 문제처럼

2차원 배열로 주어진 입력에 대해서만 bfs를 수행하다가 정수에 대한 최소 횟수를 bfs로 답을 찾아낼 수 있다는 것이 신기하고 낯설었다. bfs의 특성을 생각해보면 쉽다. a에서 b로 가는 최소 횟수를 구한다. a에서 다음 정점으로 갈 때, 방문하지 않았으면 간다. 그리고 다음 정점으로 갈 때 횟수(거리/시간)을 기록한다! a에서 b로 가는 최소 횟수(최단거리/최단시간)은 기록한 dist배열에서 b에 이르기까지 횟수를 의미하는 dist[b] 값이 정답이 된다!

=>2차원 배열 된 입력 with BFS 뿐만 아니라 Two Dots(DFS), 서울지하철 2호선(인접리스트 이용), BFS 스페셜 저지 등 풀이 방식이 다른 문제들도 익숙해질 필요가 있다! 입력이 2차원 배열이 아니라도 BFS/DFS(재귀/스택) 풀이 방법을 떠올릴 수 있도록 다양한 BFS/DFS 문제를 많이 풀어봄으로써 익숙해지자!

아래의 코드처럼 수학적으로 풀어보았는데 무한루프에 빠지는 것처럼 실행이 제대로 되지 않았다.

n을 가감하면서 while루프 탈출조건을 걸어주었는데 왜 제대로 실행되지 않는 걸까?(QnA 질문 완료, 답변 기다리는 중 6/1화)

import java.util.*;
public class Hide_Seek {
	public static int n;
	public static int k;
	public static int[] dir = {-1,1,2};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		int cnt=0;
		while(n != k) {//왜 무한루프에 빠지는가!?
			for(int i=0;i<3;i++) {
				n = n+dir[i];//이동한 새로운 좌표.
				if(i==2) {n = n*2;}
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

BFS Solution

1. 정점 : 현재 수빈의 위치, 간선 : +1/-1/X2

2. 최소 시간 찾는 BFS 탐색에 필요한 것 1. 중복 방문 방지를 위한 check 배열 2. 거리(시간)를 기록하기 위한 dist 배열

3. 이동 시간(가중치) 모두 1이지만, 이동할 때마다 이동하는 거리가 +1,-1,X2로 다 다르기 때문에 각각의 이동거리에 따라 다음 이동 정점처리를 다르게 해준다!

BFS Solution으로 풀었을 때 틀린 이유(실수)

+1,-1,*2 다음으로 이동할 정점 좌표에 대해 중복체크를 하지 않아 무한루프를 돌게 되고, 메모리 힙 공간초과 에러가 났다.