난이도 level2 문제
programmers.co.kr/learn/courses/30/lessons/1844
코딩테스트 연습 - 게임 맵 최단거리
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1
programmers.co.kr
제한사항
- maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
- n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
- maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
- 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
간단히 2차원 배열에서 1은 길이고 0은 벽이며 배열의 0,0 에서 도착지점인 n-1,m-1 까지의 최단거리를 찾는 문제다.
최단 거리를 찾는데 사용하는 알고리즘 방식중에 BFS가 있다. 이는 넓이우선탐색 으로서 자신이 위치한 곳에서 가장 근접한 곳을 탐색하는 방식이다. 그런데 여기서 조금 헷갈릴 수도 있기 때문에 실제 문제에 나온 maps를 예로 풀어보자
int [][] maps = {{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,1},{0,0,0,0,1}};
이렇게 maps를 넘겨준다. 2차원 배열을 보기좋게 정렬하고 한칸씩 이동하면서 근접한 위치를 탐색한다.
탐색 규칙은 넓이우선탐색을 사용하며 규칙은 아래와 같다.
1. 방문한 곳은 다시 방문하지 않는다.
2. 방문한 곳은 cost를 방문하기 전블럭의 cost 보다 +1 해준다.
3. 자신의 근접한 이동 경로가 있다면 Q에 넣어준다. (동/서/남/북 4가지 경로중에 최대 3곳이 들어갈 수 있다.)
(이 때 Q에 중복되는 경로가 들어 갈 수 있기 때문에 꼭 이동할 경로를 찾고 Q에 넣을 때 방문 한 위치라고 미리 표시를 해주어야 중복되는 경로를 막을 수 있다.)
4. 현재 경로가 목적지 라면 cost를 return 하고 종료한다.
하나하나 색으로 표시하면서 혹시라도 이해가 안되는 분들이 계시다면 참고 하실 수 있게 적어봤는데... 도움이 될지는 모르겠다... 부디... ㅋ
순서1 부터 시작을 하며 배열의 색과 설명에 써놓은 좌표 색을보면 매핑이 되니 차근차근 따라가다보면 이해가 될테니
조금만 인내를 하고 따라가 보시길... 참고로 순서7부터 2곳의 이동 경로가 들어 가기 때문에 이곳부터 잘~ 봐야된다.
================= 순서1 =================
최초 시작되는 위치는 0,0 이기 때문에 Q에 시작 위치를 넣어준다.
현재 Q에 들어있는 좌표 Queue = { {0,0} }
1. Q에서 가장 앞에있는 좌표를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {0,0} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {1,0}
Queue = { {1,0} }
1 0 1 1 1
1 0 1 0 1
1 0 1 1 1
1 1 1 0 1
0 0 0 0 1
========================================
================= 순서2 =================
현재 Q에 들어있는 좌표 Queue = { {1,0} }
1. Q에서 가장 앞에있는 좌표 {1,0} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {1,0} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {2,0}
Queue = { {2,0} }
1 0 1 1 1
2 0 1 0 1
1 0 1 1 1
1 1 1 0 1
0 0 0 0 1
========================================
================= 순서3 =================
현재 Q에 들어있는 좌표 Queue = { {2,0} }
1. Q에서 가장 앞에있는 좌표 {2,0} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {2,0} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {3,0}
Queue = { {3,0} }
1 0 1 1 1
2 0 1 0 1
3 0 1 1 1
1 1 1 0 1
0 0 0 0 1
========================================
================= 순서4 =================
현재 Q에 들어있는 좌표 Queue = { {3,0} }
1. Q에서 가장 앞에있는 좌표 {3,0} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {3,0} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {3,1}
Queue = { {3,1} }
1 0 1 1 1
2 0 1 0 1
3 0 1 1 1
4 1 1 0 1
0 0 0 0 1
========================================
================= 순서5 =================
현재 Q에 들어있는 좌표 Queue = { {3,1} }
1. Q에서 가장 앞에있는 좌표 {3,1} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {3,1} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {3,2}
Queue = { {3,2} }
1 0 1 1 1
2 0 1 0 1
3 0 1 1 1
4 5 1 0 1
0 0 0 0 1
========================================
================= 순서6 =================
현재 Q에 들어있는 좌표 Queue = { {3,2} }
1. Q에서 가장 앞에있는 좌표 {3,2} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {3,2} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {2,2}
Queue = { {2,2} }
1 0 1 1 1
2 0 1 0 1
3 0 1 1 1
4 5 6 0 1
0 0 0 0 1
========================================
================= 순서7 =================
현재 Q에 들어있는 좌표 Queue = { {2,2} }
1. Q에서 가장 앞에있는 좌표 {2,2} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {2,2} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {1,2}, {2,3}
Queue = { {1,2}, {2,3} }
1 0 1 1 1
2 0 1 0 1
3 0 7 1 1
4 5 6 0 1
0 0 0 0 1
========================================
================= 순서8 =================
현재 Q에 들어있는 좌표 Queue = { {1,2},{2,3} }
1. Q에서 가장 앞에있는 좌표 {1,2} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {1,2} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {0,2}
Queue = {{2,3}, {0,2} }
1 0 1 1 1
2 0 8 0 1
3 0 7 1 1
4 5 6 0 1
0 0 0 0 1
========================================
================= 순서9 =================
현재 Q에 들어있는 좌표 Queue = { {2,3},{0,2} }
1. Q에서 가장 앞에있는 좌표 {2,3} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {2,3} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {2,4}
Queue = {{0,2}, {2,4} }
1 0 1 1 1
2 0 8 0 1
3 0 7 8 1
4 5 6 0 1
0 0 0 0 1
========================================
================= 순서10 ================
현재 Q에 들어있는 좌표 Queue = { {0,2},{2,4} }
1. Q에서 가장 앞에있는 좌표 {0,2} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {0,2} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {0,3}
Queue = {{2,4}, {0,3} }
1 0 9 1 1
2 0 8 0 1
3 0 7 8 1
4 5 6 0 1
0 0 0 0 1
========================================
================= 순서11 ================
현재 Q에 들어있는 좌표 Queue = { {2,4},{0,3} }
1. Q에서 가장 앞에있는 좌표 {2,4} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {2,4} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {1,4}, {3,4}
Queue = {{0,3}, {1,4}, {3,4} }
1 0 9 1 1
2 0 8 0 1
3 0 7 8 9
4 5 6 0 1
0 0 0 0 1
========================================
================= 순서12 ================
현재 Q에 들어있는 좌표 Queue = { {0,3}, {1,4}, {3,4} }
1. Q에서 가장 앞에있는 좌표 {0,3} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {0,3} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {0,4}
Queue = {{1,4}, {3,4}, {0,4} }
1 0 9 10 1
2 0 8 0 1
3 0 7 8 9
4 5 6 0 1
0 0 0 0 1
========================================
================= 순서13 ================
현재 Q에 들어있는 좌표 Queue = { {1,4}, {3,4}, {0,4} }
1. Q에서 가장 앞에있는 좌표 {1,4} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {1,4} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = 모두 방문 했거나 벽 또는 길이 없으므로 넣을 좌표가 없다.
Queue = { {3,4}, {0,4} }
1 0 9 10 1
2 0 8 0 10
3 0 7 8 9
4 5 6 0 1
0 0 0 0 1
========================================
================= 순서14 ================
현재 Q에 들어있는 좌표 Queue = { {3,4}, {0,4} }
1. Q에서 가장 앞에있는 좌표 {3,4} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {3,4} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = {4,4}
Queue = { {0,4}, {4,4} }
1 0 9 10 1
2 0 8 0 10
3 0 7 8 9
4 5 6 0 10
0 0 0 0 1
========================================
================= 순서15 ================
현재 Q에 들어있는 좌표 Queue = { {0,4}, {4,4} }
1. Q에서 가장 앞에있는 좌표 {0,4} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {0,4} 에서 이동 가능한 좌표를 찾아서 넣어준다.
이동 가능한 좌표 = 모두 방문 했거나 벽 또는 길이 없으므로 넣을 좌표가 없다.
Queue = { {4,4} }
1 0 9 10 11
2 0 8 0 10
3 0 7 8 9
4 5 6 0 10
0 0 0 0 1
========================================
================= 순서16 ================
현재 Q에 들어있는 좌표 Queue = { {4,4} }
1. Q에서 가장 앞에있는 좌표 {4,4} 를 꺼내고 cost를 증가한다.
2. 꺼낸 좌표 {4,4} 가 목적지 이기 때문에 방문 가능한 곳을 찾지않고 cost를 return 한다.
Queue = { }
1 0 9 10 11
2 0 8 0 10
3 0 7 8 9
4 5 6 0 10
0 0 0 0 11
========================================
class SearchMaps {
public static void main(String[] args) {
// int[][] maps = {{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,1},{0,0,0,0,1}};
int[][] maps = {{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,0},{0,0,0,0,1}};
System.out.println(new SearchMaps().solution(maps));
}
/**
* BFS 넓이우선탐색을 통해 목적지를 찾고 목적지를 찾은 순간이 최단거리를 보장하기 때문에 바로 종료하면 된다.
*
*
* 1. 현재 위치에서 이동 가능한 좌표를 Queue 에 넣어준다.
* 2. Queue에 들어있는 좌표를 꺼낸다(해당 좌표에 왔었다는 표시를 하고 지나온 거리 cost를 +1 해준다.)
* 3. 다시 1번과 2번을 반복적으로 수행하면서 Queue에 들어있는 아이템을 모두 소진하면 목적지에 도달 할
* 수 없는 거라고 보면 되기 때문에 -1을 return 한다.
* 4. Queue의 목록을 모두 소진하기 전에 배열의 가장 끝 지점(maps.length-1 , maps[0].length-1)에
* 도착하면 cost를 return 하고 종료된다. > 목적지 최단거리 찾기 성공
*
*/
public int solution(int [][] maps) {
// Queue를 생성하고 출발 위치를 넣어준다. 출발은 0,0 cost = 1
Queue<Block> queue = new LinkedList<>();
queue.offer(new Block(0, 0, 1));
return bfs(queue, maps);
}
public int bfs(Queue<Block> queue, int [][] maps) {
boolean [][] isVisited = new boolean[maps.length][maps[0].length]; // 방문한 곳을 기록
Block currentBlock;
int [][] ltrb = {{-1,0},{1,0},{0,-1},{0,1}}; // 상,하,좌,우
int nextY, nextX, nextCost; // 다음좌표 Y,X cost
int dX = maps[0].length-1; // 목표좌표 X
int dY = maps.length-1; // 목표좌표 Y
isVisited[0][0] = true; // 최초 지점 방문확인
while(!queue.isEmpty()) {
currentBlock = queue.poll(); // 1. queue에 들어있는 좌표를 꺼낸다.
// 2. queue에서 꺼낸 좌표가 마지막 위치면 목적지 도달! finish
if(currentBlock.x == dX && currentBlock.y == dY)
return currentBlock.cost;
// 3. 다음에 사용 할 cost를 +1 한다.
nextCost = currentBlock.cost;
nextCost++;
// 4. 상하좌우 이동 가능한 좌표를 찾아서 Queue에 넣어준다. 가능 한 좌표가 없거나 또는 최대 3개까지 가능함.
for(int i=0; i<4; i++) {
nextX = currentBlock.x + ltrb[i][0];
nextY = currentBlock.y + ltrb[i][1];
if( nextX < 0 || nextX > dX || nextY < 0 || nextY > dY ) continue; // 배열을 벗어나면 패스
if(isVisited[nextY][nextX]) continue; // 방문한 적이 있으면 패스
if(maps[nextY][nextX] == 0) continue; // 길이 아니면 패스
// 5. 방문 한 표시를 남겨서 다시 방문하지 않는다.
isVisited[nextY][nextX] = true;
// 1. 배열 index에 포함되고 , 2.방문한 적이 없고, 3.길이 맞으면 Queue에 Block을 만들어서 넣어준다.
queue.offer(new Block(nextX, nextY, nextCost));
}
}
return -1;
}
class Block {
int y;
int x;
int cost;
Block(int x, int y, int cost) {
this.x = x;
this.y = y;
this.cost = cost;
}
}
}
와... ㅎㅎ 하나하나 작성하기 너무나 힘들다 ㅋㅋㅋㅋ
포스팅 이렇게 하는게 맞나???
'Algorithm > BFS' 카테고리의 다른 글
| 카카오프렌즈 컬러링북 (0) | 2021.05.14 |
|---|---|
| Breadth-first search 기본개념 (0) | 2021.05.05 |
