https://school.programmers.co.kr/learn/courses/30/lessons/1844
👉 문제
문제의 전체 내용을 캡쳐하기엔 다소 내용이 많으므로 위 이미지를 통해 요약 설명하겠다.
예시의 내용은 좌측의 이미지와 같이 5X5 크기의 맵에서 캐릭터가(행:1, 열:1) 위치에 있을 때, 상대 팀 진영(행:5, 열:5)위치로 도착하기 위해서 지나가야 하는 칸의 개수를 우측의 이미지와 같이 최솟값을 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를 알고 있다면 쉽게 풀 수 있다. 전체 맵 중에서 현재 위치를 기준으로 상,하,좌,우를 탐색하되, 방문하지 않았고, 맵의 값이 1인 곳 만 탐색하면 된다.
다른 방법도 있을 수 있겠지만, 필자가 생각한 방법은 dfs를 이용해 푸는 방법에서
-
visited를 2차원 int형 배열로 선언하여
visited[nx][ny] == 0 && maps[nx][ny] == 1를 만족하는 곳의 visited 값을 1 증가시킨다. -
visited를 2차원 boolean형 배열로 선언하여
visited[nx][ny] == false && maps[nx][ny] == 1를 만족하는 곳의 maps 값을 증가시킨다.
2번의 경우 maps의 방문한 곳의 값을 변경하더라도, 방문하지 않은 곳은 0이나 1이고, 그 중 1인 곳만 방문하면 되기 때문에 2차원 int형 배열을 굳이 2개나 선언하지 않아도 된다.
1. 2차원 배열 2개 이용
import java.util.*;
class Solution {
int[] dx = {0, 0, -1, 1};
int[] dy = {1, -1, 0, 0};
public int solution(int[][] maps) {
int answer = 0;
int[][] visited = new int[maps.length][maps[0].length];
bfs(maps, visited);
answer = visited[maps.length - 1][maps[0].length - 1];
if(answer == 0) answer = -1;
return answer;
}
public void bfs(int[][] maps, int[][] visited){
visited[0][0] = 1;
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0, 0});
while(!q.isEmpty()){
int[] current = q.remove();
int cx = current[0];
int cy = current[1];
for(int i=0; i<4; i++){
int nx = cx + dx[i];
int ny = cy + dy[i];
if(nx < 0 || nx > maps.length - 1 || ny < 0 || ny > maps[0].length - 1)
continue;
if(visited[nx][ny] == 0 && maps[nx][ny] == 1){
visited[nx][ny] = visited[cx][cy] + 1;
q.add(new int[]{nx, ny});
}
}
}
}
}▼ 1번 방법 결과 ▼
2. boolean형 visited와 maps 변화
import java.util.*;
class Solution {
static boolean[][] visited;
int[] dx = {0, 0, -1, 1};
int[] dy = {1, -1, 0, 0};
public int solution(int[][] maps) {
int answer = 0;
int n = maps.length;
int m = maps[0].length;
visited = new boolean[n][m];
bfs(maps);
answer = maps[n - 1][m - 1];
if(visited[n - 1][m - 1] == false) answer = -1;
return answer;
}
public void bfs(int[][] maps){
visited[0][0] = true;
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0, 0});
while(!q.isEmpty()){
int[] current = q.remove();
int cx = current[0];
int cy = current[1];
for(int i=0; i<4; i++){
int nx = cx + dx[i];
int ny = cy + dy[i];
if(nx < 0 || nx > maps.length - 1 || ny < 0 || ny > maps[0].length - 1)
continue;
if(visited[nx][ny] == false && maps[nx][ny] == 1){
maps[nx][ny] = maps[cx][cy] + 1;
visited[nx][ny] = true;
q.add(new int[]{nx, ny});
}
}
}
}
}
사실 방식은 똑같은데 'int형 배열 대신 boolean을 사용하여 메모리 사용량을 줄이는 정도라고 할 수 있겠다.' 라고 생각한 것에 비해 속도나, 메모리 차이가 별로 없다 ㅋㅋㅋ 뭐.. 암튼 그런식으로도 풀 수 있다는 점..
테스트 케이스마다 달라서 뭐가 더 좋다는 확실하게 말할 순 없겠다.. 근데 효율성 테스트로 보아하니 1번 방법이 더 나은가보다 ㅋㅋ..
