유형: 그래프 탐색 (BFS)
문제: 프로그래머스 - 게임 맵 최단거리

---

풀이

"상대 팀 진영으로 가는 가장 빠른 방법"을 찾아야 해 BFS로 풀었다.

입력이 2차원 배열로 주어져 인덱스 값 x, y 와 비용(거리) cnt 를 가진 Node 클래스를 만들어 Queue에 Node 객체를 넣었다.

static class Node {
    int x, y, cnt;

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

각 위치마다 비용이 달라 각각의 객체에 cnt 를 할당

상, 하, 좌, 우 방향 이동을 위해 dx 와 dy 배열에 4가지 값을 담았다.

int[] dx = {0, 0, -1, 1};
int[] dy = {-1, 1, 0, 0};

1. Queue에서 꺼낸 위치를 기준으로 상, 하, 좌, 우 탐색
2. 상대 팀 진영 체크 : cnt 에 +1한 값을 반환하고 함수 종료
3. 유효 범위 체크 : 범위를 벗어난 경우 다음 위치를 탐색 (continue)
4. 캐릭터 이동: 벽(0)이 아닌 곳이라면 Queue에 이동 위치와 거리 삽입
5. 방문 처리 : 해당 위치를 0으로 바꿈

상대 팀 진영을 찾지 못하고 Queue가 비었다면 -1을 반환하고 종료된다.

---

코드

import java.util.*;

class Solution {
    static class Node {
        int x, y, cnt;

        Node(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    static int bfs(int n, int m, int[][] maps) {
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0,0, 1));
        maps[0][0] = 0;

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            for (int i = 0; i < 4; i++) {
                // 상, 하, 좌, 우 방향 이동
                int pX = node.x + dx[i];
                int pY = node.y + dy[i];

                // 상대 팀 진영 체크
                if (pX == n && pY == m) {
                    return node.cnt+1;
                }

                // 유효 범위 체크
                if (pX < 0 || pY < 0 || pX > n || pY > m) {
                    continue;
                }

                // 캐릭터 이동
                if (maps[pX][pY] == 1) {
                    queue.offer(new Node(pX, pY, node.cnt+1));
                    maps[pX][pY] = 0; // 방문 체크
                }

            }
        }
        return -1;
    }
    
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;

        return bfs(n-1, m-1, maps);
    }
}

---

문제

입출력