[프로그래머스 | lv2 | DFS/BFS] 게임 맵 최단거리

게임 맵 최단거리

dfs 사용상황 :각 정점에 숫자가 있고, A부터B까지의 경로를 구하는데 경로에 같은 숫자가 있으면 안된다.

✔ 아이디어
1. 상하좌우 이동을 표현하는 방향벡터(dx, dy) 필요
2. DFS 사용으로 인한 Queue 사용
3. 방문처리여부(visited)에 지금까지 지나온 누적거리값이 할당되어야함. => 현재 좌표에서의 visited에 1을 더하여 구현

visited[next_x][next_y] = 1+visited[cur_x][cur_y];//방문처리

---

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

class Solution {
    int[] dx = {0, 0, -1, +1};
    int[] dy = {-1, +1, 0, 0};
    
    
     // 상대진영에 도달할 수 없으면 -1리턴하라고 했기에

    public void bfs(int x, int y, int[][] maps,int [][]visited) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(x, y));
        visited[x][y] = 1;
    
            while (!queue.isEmpty()) {
                Node node = queue.poll();//최상단 노드 꺼내서 현재 위치로 설정
                int cur_x = node.x;
                int cur_y = node.y;

                for (int i = 0; i < 4; i++) {
                    int next_x = dx[i] + cur_x;//다음 좌표 위치 구하기
                    int next_y = dy[i] + cur_y;

                    if (next_x <0 || next_y < 0 || next_x > maps.length-1 || next_y > maps[0].length-1) continue;//맵을 벗어나면 x
                    if (visited[next_x][next_y]!=0|| maps[next_x][next_y] == 0) continue;//이미 방문했거나 장애물이 있다면 
                    else {
                        visited[next_x][next_y] = 1+visited[cur_x][cur_y];//방문처리
                    	queue.offer(new Node(next_x, next_y));//다음위치 큐에 넣   
                    }
              	}
			}
    	}

    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int solution(int[][] maps) {
        int[][] visited = new int[maps.length][maps[0].length];
        bfs(0, 0, maps,visited);
        int result = visited[maps.length-1][maps[0].length-1];
        if (result==0) return -1;
        return result;
    }
}

함수

DFS

: 기존의 DFS와 동일하나, 방문처리시 boolean 값이 아닌 지금까지의 거리를 누적한 값을 할당함.

public void bfs(int x, int y, int[][] maps,int [][]visited) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(x, y));
        visited[x][y] = 1;
    
            while (!queue.isEmpty()) {
                Node node = queue.poll();//최상단 노드 꺼내서 현재 위치로 설정
                int cur_x = node.x;
                int cur_y = node.y;

                for (int i = 0; i < 4; i++) {
                    int next_x = dx[i] + cur_x;//다음 좌표 위치 구하기
                    int next_y = dy[i] + cur_y;

                    if (next_x <0 || next_y < 0 || next_x > maps.length-1 || next_y > maps[0].length-1) continue;//맵을 벗어나면 x
                    if (visited[next_x][next_y]!=0|| maps[next_x][next_y] == 0) continue;//이미 방문했거나 장애물이 있다면 
                    else {
                        visited[next_x][next_y] = 1+visited[cur_x][cur_y];//방문처리
                    	queue.offer(new Node(next_x, next_y));//다음위치 큐에 넣   
                    }
              	}
			}
    	}

class : Node 좌표를 한번에 표현하기 위한 클래스

static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

main

public int solution(int[][] maps) {
        int[][] visited = new int[maps.length][maps[0].length]; //주어진 미로의 크기를 받아서 방문처리 만들기
        bfs(0, 0, maps,visited);//시작위치에서 dfs 시작
        int result = visited[maps.length-1][maps[0].length-1];//마지막 위치에서의 방문처리(거리누적값) 반환
        if (result==0) return -1;//문제에 따라 도달할 수 없는 경우에 -1반환
        return result;
    }