2178_미로 탐색 (JAVA) (C++)

2178번: 미로 탐색

 

[C++]

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

int row, col;
int map[101][101];
bool visited[101][101];
int ans = 0;

struct XY{
    int x;
    int y;
};
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

void bfs(int a, int b){
    queue<XY> q;
    q.push({a,b});
    visited[a][b] = true;
    
    while(!q.empty()){
        XY cur = {q.front().x, q.front().y};
        q.pop();
        
        for(int i=0; i<4; i++){
            XY next = {cur.x+dx[i], cur.y+dy[i]};

            if(next.x>=0&&next.x<row && next.y>=0&&next.y<col){
                if(!visited[next.x][next.y] && map[next.x][next.y]==1){
                    map[next.x][next.y] = map[cur.x][cur.y]+1;
                    visited[next.x][next.y] = true;
                    q.push(next);
                }
            }
        }
    }
}

int main(){
    cin >> row >> col;

    for(int i=0; i<row; i++){
        string str;
        cin >> str;

        for(int j=0; j<str.length(); j++){
            map[i][j] = str.at(j)-'0';
        }
    }

    bfs(0,0);
    cout << map[row-1][col-1];

    return 0;
}

 

 

[JAVA]

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	static int N;
	static int M;
	static int[][] miro;
	static int[][] visited;
	static int dx[]={-1, 1, 0, 0};
	static int dy[]={0, 0, -1, 1};
	
	static class XY{
		int x;
		int y;
		public XY(int x, int y){
			this.x = x; this.y = y;
		}
	}
	
	
	public static void main (String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); M = sc.nextInt();
		miro = new int[N][M];
		visited = new int[N][M];
		
		for(int i=0; i<N; i++){
			String temp = sc.next();
			for(int j=0; j<M; j++){
				miro[i][j] = temp.charAt(j)-'0';
			}
		}
		
		Queue<XY> q = new LinkedList<XY>();
		q.offer(new XY(0,0)); //시작점
		visited[0][0]=1;
		
		while(!q.isEmpty()){
			int x = q.peek().x;
			int y = q.peek().y;
			q.poll();
			
			for(int i=0; i<4; i++){
				int xx = x + dx[i];
				int yy = y + dy[i];
				
				if((xx>=0&&xx<N) && (yy>=0&&yy<M)){
					if(miro[xx][yy]==1 && visited[xx][yy]==0){
						miro[xx][yy] = miro[x][y]+1;
						q.offer(new XY(xx,yy));
						visited[xx][yy]=1;
					}
				}
			}
		}
		
        System.out.println(miro[N-1][M-1]);
				
	}
}

1. '최소' 칸 수를 출력해야된다고 해서- BFS로 풀었다. (단순ㅎㅎ)

2. 배열에서의 움직임을 (x,y)로 생각해 풀어야되니까, (x,y)로 구성되는 XY클래스 만들었다.

3. 입력: '각각의 수들은 "붙어서" 입력으로 주어진다.'

   각 줄마다 string으로 입력을 받고, 각 자리의 char형을 int형으로 바꿔서 배열에 저장했다.

  ( miro[i][j] = temp.charAt(i)-'0'; ) 

4. dx, dy로 방향 이동하도록했고, 이동할 수 있는 자리에 가게되면(miro[i][j]==1)

   miro[xx][yy] = miro[x][y]+1; 로 이전 자리 숫자에 +1해서 miro배열에다가 적어놓고,

   나중에는 [N-1][M-1]자리 숫자 출력했다.