[JAVA] 프로그래머스 - 게임 맵 최단거리

문제내용

https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

---

문제 접근 방법

이번 문제는 대표적인 BFS 문제이다. 이전에 백준에서 미로찾기, 토마토 등의 문제들을 풀어봤기 때문에 접근하는데 어려움은 없었다.

그리고 이문제를 푸는 BFS 방법은 두가지가 있다고 생각한다.

두가지의 문제풀이를 간단하게 설명해보자면 아래와같다.

 

첫번째는 BFS를 돌리면서 (x, y, 거리) 를 큐에 저장해줄 수 있는 클래스 객체를 하나 만드는것.

두번째는 BFS를 돌리면서 x좌표를 저장해줄 큐하나, y좌표를 저장해줄 큐하나해서 총 두개의 큐를 만드는것.

두가지가 있다.

 

첫번째 방법은 BFS가 한번 돌때마다 해당좌표까지 얼마나 이동됐는지 거리를 저장해놓기 때문에 목적지까지 BFS가 돌았을때의 거리를 큐에서 뽑아내면 정답이다. 만약 목표지점까지 BFS가 돌지 못했다면 -1을 반환하면 된다.

 

두번째 방법도 첫번째 방법과 마찬가지의 원리이다. 다만 객체대신 하나의 큐에 x좌표, 또다른 큐에 y좌표를 넣어주면 된다. 그리고 x,y 좌표가 목표지점과 동일해졌을때 거리를 뽑아주면된다. 이때 거리는 입력받은 maps배열에서 BFS가 한번 돌때마다 1을 증가시키거나 maps배열을 복사해서 같은 방법으로 한번돌때마다 1을 증가시키면 목표지점까지 갔을때의 원하는 거리가 나오게된다.

 

BFS를 알고 있다는 전제하에 말해놓은거라 이해가 안간다면 BFS를 먼저 공부해보길 바란다.

그리고 나는 첫번째 방법으로 풀었다.

 

풀이를 보자.

 

---

풀이

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
	static int[] dx = {-1,1,0,0};//상하
	static int[] dy = {0,0,-1,1};//좌우
	static boolean[][] check;//방문배열
	
	public static int solution(int[][] maps) {
		int answer = -1;
		check = new boolean[maps.length][maps[0].length];
		Queue<PointXY> q = new LinkedList<PointXY>();
		
		//시작은 (0,0)에서 시작, 처음에 거리는 1로 초기화
		q.add(new PointXY(0, 0, 1));
		check[0][0]=true;//첫번째 좌표 방문처리
		
		//bfs 시작
		while(!q.isEmpty()) {
			PointXY p = q.poll();
			int nowX = p.x;
			int nowY = p.y;
			int nowD = p.dis;
			
			//목표지점까지 갔을때 answer에 해당지점까지 움직인거리 넣고 종료.
			if(nowX==maps.length-1 && nowY==maps[0].length-1) {
				answer = nowD;
				break;
			}
			
			//상하좌우탐색
			for(int i=0; i<4; i++) {
				int nextX = nowX + dx[i];
				int nextY = nowY + dy[i];

				//인덱스가 배열의 크기안에 있을때
				if(nextX>=0 && nextY>=0 && nextX<maps.length && nextY<maps[0].length) {
					//벽이 아니고 방문안한 좌표라면
					if(maps[nextX][nextY]==1 && !check[nextX][nextY]) {
						q.add(new PointXY(nextX, nextY, nowD+1));
						check[nextX][nextY]=true;
					}
				}
			}//for
		}//while
		
		return answer;
	}
}

//x,y좌표와 해당 좌표일때의 움직인거리(dis)를 나타내는 클래스
class PointXY{
	int x;
	int y;
	int dis;
	public PointXY(int x, int y, int dis) {//생성자
		this.x = x;
		this.y = y;
		this.dis = dis;
	}
}

 

---

마치며

BFS를 안다면 어렵지 않은 문제이다. 이번 문제는 복습하는 문제였다고 생각한다.