[프로그래머스] 게임맵 최단거리 (C++, JAVA)

https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

레벨 : Level 2

전형적인 bfs문제로 추가설명은 생략 :) 

#include <iostream>
#include<vector>
#include <queue>
using namespace std;

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

//bfs
int solution(vector<vector<int> > maps)
{
    int N = maps.size();
    int M = maps[0].size();
    queue<pair<int, int>>q;
    q.push({ 0,0 });
    visit[0][0] = 1;
    int answer = 0;

    while (!q.empty()) {
        int size = q.size();
        answer++;
        while (size--) {
            int x = q.front().first;
            int y = q.front().second;
            if (x == N - 1 && y == M - 1) return answer;
            q.pop();
            for (int i = 0; i < 4; i++){
                int cx = x + dx[i];
                int cy = y + dy[i];
                if (cx >= 0 && cx < N && cy >= 0 && cy < M && maps[cx][cy] && !visit[cx][cy]) {
                    visit[cx][cy] = 1;
                    q.push({ cx,cy });
                }
            }
        }      
    }
    return -1;
}

import java.util.*;

class Solution {
    int[] dx = {0,0,1,-1};
    int[] dy={1,-1,0,0};
    int N,M;
    class Node{
        int x;
        int y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public int solution(int[][] maps) {
        int answer = 0;
        N=maps.length;
        M=maps[0].length;
        boolean[][] visit = new boolean[N][M];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0,0));
        visit[0][0]=true;
        while(!q.isEmpty()){
            answer++;
            int size = q.size();
            for(int j=0; j<size; j++){
                Node cur = q.poll();
                if(cur.x==N-1 && cur.y==M-1) return answer;
                for(int i=0; i<4; i++){
                    int cx = cur.x+dx[i];
                    int cy = cur.y+dy[i];
                    if(cx>=0 && cx<N && cy>=0 && cy<M 
                       && !visit[cx][cy] && maps[cx][cy]==1){
                        visit[cx][cy]=true;
                        q.add(new Node(cx,cy));
                    }
                }
            }
            
        }
        return -1;
    }
}