[게임 맵]

 

 

나의 첫 dfs/bfs 문제. 진짜 개념을 아직도 잘 모르겠다. 어찌되었든 너무 어려웠고 구글링해서 나왔던 다른 사람들 풀이법도 많이 어려웠기에 그중에서 가장 그나마 이해할 수 있었던 코드를 정리해두었다. 내 것으로 만들려면 최소 백 번쯤은 더 보아야 할 것 같다.

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

public class GameMap {
    public static void main(String[] args) throws Exception {
        Solution solution = new Solution();
        int[][] numbers = {{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}};
        System.out.println(solution.solution(numbers));
    }
}

class Solution {
    // 4방향 위치좌표 생성
    int[][] dRowCol = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; //상우하좌
    
    // maps 저장할 2차원 배열 생성
    int[][] graph;
    
    int answer;

    public int solution(int[][] maps) {
        //graph 에 maps 지정
        graph = maps;
        //최단 거리를 구해야 하므로 초기값을 int의 최대값으로 지정
        answer = Integer.MAX_VALUE;

        //dfs 메서드 실행
        dfs();

        //answer를 return
        return answer;
    }

    private void dfs() {
        Queue<MyCharacter> queue = new LinkedList<>();
        
        queue.add(new MyCharacter(0, 0, 1)); // 위치좌표, 내가 지나온 칸 수
        graph[0][0] = 0;

        //Queue가 빌때까지 while문을 실행
        while (!queue.isEmpty()) {
        
            //Queue 안에 들어있던 원소를 하나 꺼냄
            MyCharacter tempCharacter = queue.poll(); 
            // poll : 큐 맨 앞에 있는 값 반환 후 삭제 / 큐가 비어있을 경우 null 반환
            
            //원소의 멤버 모두 꺼내서 임시변수로 저장
            int tempRow = tempCharacter.getRow();
            int tempCol = tempCharacter.getCol();
            int tempCount = tempCharacter.getPathCount();

            //원소의 좌표가 목적지에 도달하면 answer를 업데이트
            //최단 거리를 구해야하므로 Math.min 을 사용
            if (tempRow == (graph.length - 1) && tempCol == (graph[0].length - 1))
                answer = Math.min(answer, tempCount);

            //4방향으로 돌면서 Queue에 넣어줄 원소 찾기
            for (int i = 0; i < dRowCol.length; i++) {
                //아까 꺼낸 원소의 좌표에다가 4방향 이동하면 변하게 될 좌표를 더해서 이동시의 좌표를 구한다.
                int tempRow2 = tempRow + dRowCol[i][0];
                int tempCol2 = tempCol + dRowCol[i][1];
                //옮겨지는 좌표가 Matrix의 범위를 벗어나지 않고 , 방문처리가 되어있지 않으면
                // Queue 의 원소로 집어넣고 , 방문처리를 한다.
                
                if (!isOutOfMatrix(tempRow2, tempCol2) && graph[tempRow2][tempCol2] == 1) {
                    //Queue에 데이터를 집어넣기
                    queue.add(new MyCharacter(tempRow2, tempCol2, tempCount + 1));
                    //visited 처리
                    graph[tempRow2][tempCol2] = 0;
                }
            }
        }

        //목적지에 도달하지 못해서 단 한번도 업데이트가 되지 못한 경우 -1을 return 
        if (answer == Integer.MAX_VALUE)
            answer = -1;
    }

    //맵 밖으로 벗어났는지 확인하기
    private boolean isOutOfMatrix(int row, int col) {
        return row < 0 || col < 0 || row >= graph.length || col >= graph[0].length;
    }
}

//Queue에 넣을 클래스 생성
class MyCharacter {
    int row;
    int col;
    int pathCount;

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getPathCount() {
        return pathCount;
    }

    public MyCharacter(int row, int col, int pathCount) {
        this.row = row;
        this.col = col;
        this.pathCount = pathCount;
    }
}