[프로그래머스/알고리즘] 게임 내 최단 거리

해결방법

미로찾기 문제인데, 상하좌우로 길이 있는지 방문합니다. 길이 있으면 BFS로 데이터를 집어 넣고 

한개씩 빼면서 그 다음 곳을 방문하는 것을 반복하면 됩니다.

DFS로 하면 깊이탐색이기 때문에 최악의 거리가 나올 가능성이 많기 때문에 사용하시면 안됩니다.

 

BFS는 주변부터 탐색이기 때문에 탐색하면서 최종 도착지가 나오면 그 값이 최단 거리이기 때문입니다.

 

이번에는 자바로 해봤습니다.

소스코드

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;

public class Solution {
	public static void main(String[] args) {
	int[] x = { 0, 0, -1, 1 };
	int[] y = { 1, -1, 0, 0 };
	int visit[][];
	public int solution(int[][] maps) {
		int answer = -1;
		int count=1;
		visit = new int[maps.length][maps[0].length];
		Deque<Data> position = new ArrayDeque<>();
		Data end = new Data(maps[0].length, maps.length);
		Data start = new Data(0, 0);
		visit[0][0]=1;
		position.add(start);
		while (!position.isEmpty()) {
			Data data = position.pollFirst();
			for (int i = 0; i < 4; i++) {
				if (overflow(data.xpos, x[i], data.ypos, y[i],maps, end)) {	//경계 밖 처리
					Data next=new Data(data.xpos+x[i],data.ypos+y[i]);
					
					if(data.xpos+x[i]==end.xpos-1&&data.ypos+y[i]==end.ypos-1) {	//결과 값
						answer=visit[data.ypos][data.xpos]+1;
						return answer;
					}
					
					if(visit[data.ypos+y[i]][data.xpos+x[i]]==0) {	//방문
						position.addLast(next);
						System.out.println("x="+(data.xpos+x[i])+"  y="+(data.ypos+y[i]));
						visit[data.ypos+y[i]][data.xpos+x[i]]=visit[data.ypos][data.xpos]+1;
					}
					
				}
			}
		}
		return answer;
	}

	public boolean overflow(int x1, int x2, int y1, int y2,int[][] maps, Data end) {
		if (x1 + x2 < 0 || x1 + x2 >= end.xpos) return false;
		if (y1 + y2 < 0 || y1 + y2 >= end.ypos) return false;
		if(maps[y1+y2][x1+x2]==0) return false;
		return true;
	}

}

class Data {
	public int xpos;
	public int ypos;

	public Data(int xpos, int ypos) {
		this.xpos = xpos;
		this.ypos = ypos;
	}
}