게임 맵 최단거리
public class 게임_맵_최단거리 {
static int answer = 0;
//x,y는 현재위치
//n,m은 전체 길이
public static int dfs(int[][] maps,int x, int y, int n, int m, int sum){
if(x < 0 || x > n-1 || y < 0 || y > m-1){
return 0;
}
if(x == n-1 && y == m-1){
answer = ++sum;
System.out.println("x = " + x+"y = " + y);
System.out.println("sum = " + sum);
return answer;
}
System.out.println("(" + x+", " + y+") sum = "+sum);
if(maps[x][y] == 0){
return 0;
}
if(maps[x][y] == 1){
maps[x][y] = 0;
sum++;
dfs(maps, x + 1, y , n , m, sum);
dfs(maps, x, y + 1 , n , m, sum);
dfs(maps, x - 1, y , n , m, sum);
dfs(maps, x, y - 1 , n , m, sum);
}
return 0;
}
public static int solution(int[][] maps) {
int n = maps.length;
int m = maps[0].length;
int sum = 0;
if(maps[n-2][m-1] == 0 && maps[n-1][m-2] == 0){
return -1;
}
int dfs = dfs(maps, 0, 0, n, m, sum);
System.out.println("dfs = " + dfs);
return answer;
}
public static void main(String[] args) {
System.out.println(solution(new int[][]
{
{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}
}));
}
}
dfs로 풀어봤는데 시간초과가 나고 틀린 부분이 나옵니다. dfs로 풀면 (n,m)에 도착을 해도 남아 있는 1 부분이 있다면 탐색을 하기 때문에 시간초과가 난다고 생각했습니다.
어떤식으로 풀어야지 한번 지나간 길을 false로 다시 만들지? 에 대한 고민을 했고 아래쪽에 답이 있습니다.
그리고 정확성도 잘 안나오는데 왜냐하면 찾아봤더니 (n,m)까지 가는데 거리가 최단경로가 아닐 수 있다는 것입니다.
public class 게임_맵_최단거리 {
static int answer = 0;
//x,y는 현재위치
//n,m은 전체 길이
public static int dfs(int[][] maps,int x, int y, int n, int m, int sum, int[][] clone){
clone[x][y] = sum;
int[] dx = {-1,1,0,0};
int[] dy = {0,0,1,-1};
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if(0 <= xx && xx < n && 0 <= yy & yy < m && maps[xx][yy] == 1 && clone[xx][yy] > sum+1){
dfs(maps,xx,yy,n,m,sum+1,clone);
}
}
System.out.println("(" + x+", " + y+") sum = "+sum);
return 0;
}
public static int solution(int[][] maps) {
int n = maps.length;
int m = maps[0].length;
int[][] clone = new int[n][m];
for (int i = 0; i < maps.length; i++) {
for (int j = 0; j < maps[0].length; j++) {
clone[i][j] = 10001;
}
}
if(maps[n-2][m-1] == 0 && maps[n-1][m-2] == 0){
return -1;
}
dfs(maps, 0, 0, n, m, 1, clone);
return clone[n-1][m-1];
}
public static void main(String[] args) {
System.out.println(solution(new int[][]
{
{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}
}));
}
}
다른분의 코드를 보고 dfs로 구현해봤습니다. clone 배열은 전부 10001값으로 채워져 있습니다. 그리고 dfs에서는 (-1,0), (1,0),(0,1),(0,-1) 순으로 좌표를 옮겨가면서 내가 방문한 것인지 아닌지 확인합니다.
문제의 예시로
처음에 clone에 있는 값이 한번 들어가면 sum값으로 바뀝니다. 그러면
&& clone[xx][yy] > sum+1if문의 이 조건과 맞지 않게됩니다.
결국 dfs가 아니라 bfs 로 최소거리를 구해야 합니다.
BFS로 구하기
public static int solution(int[][] maps) {
int n = maps.length;
int m = maps[0].length;
boolean[][] visited = new boolean[n][m];
Queue<int[]> queue = new LinkedList<>();
visited[0][0] = true;
queue.add(new int[] {0,0,1}); //{현재 위치, 현재위치, 총 수}
int[] dx = {-1,1,0,0};
int[] dy = {0,0,1,-1};
int answer = 0;
while(queue.isEmpty() == false){
int[] currPoint = queue.remove();
if(currPoint[0] == n-1 && currPoint[1] == m-1){
return currPoint[2];
}
for (int i = 0; i < 4; i++) {
int xx = dx[i] + currPoint[0];
int yy = dy[i] + currPoint[1];
if(xx >= 0 && xx < n && yy >= 0 && yy < m){
if(maps[xx][yy] == 1 && !visited[xx][yy]){
visited[xx][yy] = true;
queue.add(new int[] {xx, yy, currPoint[2]+1});
}
}
}
}
return -1;
}
많은 고민을 했습니다. 어떤식으로 동작하는지 감이 왔지만 그걸 코드로 구현하고 어디에다가 저장하는지 정하는게 어려웠습니다.
Queue 안에 int[]를 생성합니다. 여기에는 [다음x, 다음y, 걸어온count] 가 됩니다. 다음 좌표를 for문으로 돌면서 다음 좌표값이 **범위 안에 있고, 길이있고, 방문하지 않았다면** queue에 넣으면 됩니다. 이 때 주의해야할 점이 **visitied**를 true로 하고 넣어야 하는 점입니다.
혹시 본인의 코드가 방문체크를 큐에서 꺼낼 때 하고있는건 아닌지 확인해보세요.
방문체크를 큐에 넣을 때 해야 효율성이 통과됩니다.
그 이유는 만약 꺼낼 때 방문체크를 하게되면, 하나의 블럭을 꺼내서 통로를 탐색할 때, 이미 큐에 들어있는 블럭을 또 큐에 넣을 수도 있기 때문입니다.
| 1 | 0 | 9 | 10(1) | 11 |
| 2 | 0 | 8 | 0 | 10(2) |
| 3 | 0 | 7 | 8 | 9 |
| 4 | 5 | 6 | 0 | 10(3) |
| 0 | 0 | 0 | 0 | 11 |
이 문제의 예시를 예로 들면,
각 블럭의 숫자는 BFS로 탐색되는 차례입니다.
큐에서 10(1)을 먼저 꺼낸다고 하면, 10(1)은 11을 큐에 넣겠죠.
그럼 이제 큐에서 10(2) 가 꺼내집니다.
그런데 10(2)는 11을 아직 방문하지 않은 블럭이라고 판단하고 다시 큐에 넣게 됩니다.
이런 중복을 없애기 위해 큐에 넣을 때 방문했다고 체크해야 합니다.
다른 분의 dfs로 푼 코드입니다.
// dfs로 풀었을 때 효율성 문제 발생
public class shortest_gamemap {
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,0},{0,0,0,0,1}};
shortest_gamemap s = new shortest_gamemap();
System.out.println(s.solution(maps));
}
static int min;
static boolean visit[][];
static int[] dx = {-1,0,0,1};
static int[] dy = {0,1,-1,0};
public int solution(int[][] maps){
min = Integer.MAX_VALUE;
visit = new boolean[maps.length][maps[0].length];
dfs(0,0,maps,0);
if(min == Integer.MAX_VALUE){
return -1;
}
return min;
}
public void dfs(int x, int y, int[][] maps,int cnt){
cnt++;
if(x == maps.length-1 && y == maps[0].length-1){
min = Math.min(cnt, min);
return;
}
for(int i = 0; i<4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || ny <0 || nx >= maps.length || ny>= maps[0].length) continue;
if(!visit[nx][ny] && maps[nx][ny] == 1){
visit[nx][ny] = true;
dfs(nx,ny,maps,cnt);
visit[nx][ny] = false;
}
}
}
}1개의 좌표를 따라 쭉 따라가고 visit을 true로 만든 뒤 하나의 dfs스택이 끝났을 때 visit를 false로 만드는 법을 배웠습니다. 이런식으로 하면 여러개의 길을 찾을 수 있을거 같습니다.
갈림길이 나오면 하나의 길로 쭉 dfs로 들어가고, 끝에 다다르면 cnt값을 반환하고 stack을 반환합니다. 그 과정에서 visit했던것을 false로 바꿔줍니다.
즉, 갈림길이 나오면 각 길을 따라 갑니다. 그 과정에서 true를 했던것을 false로 바꾸면 모든 갈림길을 끝까지 갈 수 있습니다.
출처
'알고리즘 > Programmers' 카테고리의 다른 글
| [Programmers / Java] 소수 구하기(조합) (0) | 2022.05.24 |
|---|---|
| [Programmers / Java] 다트 게임 (0) | 2022.05.12 |
| [Programmers / Java] 멀쩡한 사각형 (0) | 2022.05.07 |
| [Programmers / Python] 메뉴 리뉴얼 (0) | 2022.03.04 |
| [Programmers / Python] 괄호변환 (0) | 2022.03.03 |
