자바 미로 문제 - jaba milo munje

Question

문제 바로가기

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

어우 10개월 전에 풀었던 건데 자바로 한 번 풀어보았씁니다.

아직 자바가 익숙치 않아 코드가 이쁘지 않기 때문에 혹시 조언해주실게 있으면 댓글에 남겨주세욥

BFS 문제를 풀겠다고 다짐하고 거의 처음 접한 문제였는데, 맨 처음 풀이 방법을 찾아 보고 이마를 탁 쳤던 기억이 납니다. n방문 여부만(true/false) 체크하는 문제만 봤었는데, next 좌표에 왔을 때 cur 좌표에 있는 visited 값 + 1 해서 이동 거리(혹은 시간)을 구하는 건 누가 생각한걸까여

세상엔 참 똑똑하신 분이 많습니다

요런 로직만 생각하면 아아아주 쉽게 풀 수 있습니다. 0이면 가지말고 1이면 가도록 해서, visited[N][M]의 값이 정답이 됩니다.

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Dir{
    int y;
    int x;
    Dir(int y, int x){
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static int N;
    static int M;
    static int [][] map;
    static int [][] visited;
    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};

    public static boolean isIn(Dir dir){
        if(0<= dir.y && dir.y < N && 0<= dir.x && dir.x < M) return true;
        else return false;
    }
    //BFS
    public static int solve(){
        int ans = 0;
        Queue<Dir> q = new LinkedList<>();

        q.offer(new Dir(0, 0));
        visited[0][0] = 1;

        while(!q.isEmpty()){
            Dir cur = new Dir(q.peek().y, q.peek().x);
            q.poll();

            for(int i=0;i<4;i++){
                Dir next = new Dir(cur.y + dy[i], cur.x + dx[i]);
                if(!isIn(next)) continue;
                if(visited[next.y][next.x] != 0) continue;
                if(map[next.y][next.x] != 1) continue;

                q.offer(next);
                visited[next.y][next.x] = visited[cur.y][cur.x] + 1;
            }
        }

        ans = visited[N-1][M-1];
        return ans;
    }

    public static void main(String[] args) throws IOException {
        Scanner input = new Scanner(System.in);
        N = input.nextInt();
        M = input.nextInt();
        map = new int[N][M];
        visited = new int[N][M];

        for(int i=0;i<N;i++){
            String temp = input.next();
            for(int j=0;j<M;j++){
                map[i][j] = temp.charAt(j)-'0';
                visited[i][j] = 0;
            }
        }

        System.out.print(solve());
    }
}

Dir: 좌표 클래스입니다. 코드가 쪼까 더러워지지 않나 고민도 했는데 낫배드한 거 같슴다
isIn: 좌표가 map 밖으로 튀어나가는지 확인해주는 메소드입니다.

2차원 map에서 상하좌우 네 방향만 체크해주면서 1이면 이동하고, 0이면 가지않도록 해서 끝까지 따라가주면 됩니다.

감사합니다.

-내 생각

알고리즘 공부를 시작하고 코딩 테스트에서 자주 나온다는 최단경로 문제를 처음으로 풀어보았는데.. 이전에 여러 글들을 보면서 최단거리 문제의 경우에는 BFS만을 이용해서 풀 수 있다고 알고 있었기 때문에 BFS를 사용하려고 했지만, 어떻게 구현해야 할지 감이 잡히지 않았다. 기본적인 흐름은 앞선 DFS문제들과 마찬가지로 인접한 좌표를 탐색하는 것부터 시작해야 한다고 생각했고, 각 경로마다 이동할 때마다 카운트해주어서 분기점에서 갈라진 경로마다의 카운트 변수를 비교해 최솟값을 찾으려고 했는데, 이것도 생각만 했지 구현도 완벽하게 하지 못했다. 2시간 정도 고민해보고 도저히 안될 것 같아 다른 여러 블로그들을 참고했는데,

하단의 Idgeao99님 블로그에서 힌트를 얻을 수 있었다. 혹시라도 막히는 분들은 참고하시면 좋을 것 같다.

https://ldgeao99.tistory.com/400?category=864321

챕터6-5. 그래프 | 문제풀이(2) - 플러드필 알고리즘(DFS, BFS 탐색응용)

플러드필 알고리즘 - 어떤 배열을 채우는 알고리즘이며, 어떤 위치와 연결된 모든 위치를 찾는 알고리즘이다. - dx, dy 가 사용됨. 유형1. 동시에 진행되는 탐색이 1개뿐인 것 # 단지에 번호를 붙이는 문제 - http..

ldgeao99.tistory.com

또 다른 문제점이 하나 더 있었는데, BFS를 구현할 때 큐를 사용해야 하는데, 큐에 어떻게 좌표값을 저장할까 였는데, 처음에는 ArrayList에 담아 ArrayList를 큐에 넣을 생각을 했었는데, 바보 같은 생각이었고 그냥 클래스를 하나 만들어 객체를 큐에 저장하면 됐다.... ㅋㅋㅋ

-해법

Idgeao99님 블로그에서 얻은 힌트는 각 원소를 방문했는지 여부를 체크하는 체크 배열에 해당 배열까지 이동한 경로를 저장한 후 마지막 배열의 원소를 출력해주면 되는 것이었다. 이 방법을 보고 무작정 공백큐가 될 때까지 반복할 때마다 카운트를 해주었더니 정답이 아닌 경로로 이동해도 카운트가 돼버리는 문제점이 있어 조금 고민해보니 그 답이 나왔다. 아래 코드를 보면서 이해해보자.

import java.util.*;


class xy{ //xy좌표 저장 클래스
	int x;
	int y;
	
	public xy(int x,int y) {
		this.x= x;
		this.y =y;
	}
}

public class Main {
	static int node[][]; // 2차원 미로 배열
	static int check[][]; // 2차원 방문여부 배열
	static int cnt =1; // 시작점인 (1,1)은 카운트된 상태로 시작하기 때문에 1로 초기화
	static int n,m;
	
	
	public static void bfs(int a,int b) { //BFS메소드
		Queue<xy> queue = new LinkedList<>(); // 큐
		a-=1; // 시작점이 1,1로 들어오므로 -1한 상태를 저장해준다.
		b-=1;
		check[a][b]= cnt; // 초기 cnt변수 값을 방문배열에서 시작점에 저장한다.
		
		queue.offer(new xy(a,b)); // 시작점의 객체를 큐에 삽입
		while(!queue.isEmpty()) { // 이제 큐가 공백이 될 때 까지 반복한다.
			int x = queue.peek().x; // 큐에 저장되어 있는 객체에서 x,y좌표를 저장
			int y = queue.peek().y;
			queue.poll(); // 큐에서 peek후 저장한 것이기 때문에 별도이 poll()수행으로 해당 객체 소멸
			
					//아래의 조건문은 DFS게시글에서 사용한 조건문과 동일
                    //다른분들은 별도의 2개 배열로 동,서,남,북을 탐색하는 방법을 사용하는데 
                    //나중에 시간을 내어 분석 해봐야겠다.
					if(y<node[x].length-1&&node[x][y]==1&&node[x][y+1]==1 && check[x][y+1]==0) {
						check[x][y+1]=check[x][y]+1; // 현재 점이 가지고 있는 경로값을 인접한 점의 방문배열에 저장 
						queue.offer(new xy(x,y+1)); // 인접한 점을 큐에 넣어준다.
					//아래는 모두 이와 동일
					}
					 if(x<node.length-1&&node[x][y]==1&&node[x+1][y]==1 && check[x+1][y]==0) {
						check[x+1][y]=check[x][y]+1;
						
						queue.offer(new xy(x+1,y));
						
					}  if(x>0&&node[x][y]==1&&node[x-1][y]==1 && check[x-1][y]==0) {
						check[x-1][y]=check[x][y]+1;
						
						queue.offer(new xy(x-1,y));
						
					}
					 if(y>0&&node[x][y]==1&&node[x][y-1]==1 && check[x][y-1]==0) {
						check[x][y-1]=check[x][y]+1;
						queue.offer(new xy(x,y-1));
						
					}
					 
					
					 
					
				}
			
			
		
		
	}
			
			
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		
		 n = sc.nextInt();
		 m = sc.nextInt();
		node = new int [n][m];
		check = new int[n][m];
		for(int i=0;i<n;i++) { // 줄단위로 입력이 이루어질 때 값을 저장하는 방식
			String row = sc.next();
			for(int j=0;j<m;j++) {
				
				node[i][j] = row.charAt(j)-'0';
			}
		}
		
		
		
		bfs(1,1); // 시작점 전달
		
		System.out.println(check[n-1][m-1]); // 방문배열의 마지막 원소 즉, 도착지점의 값을 반환하면 
        									// 그것이 최단경로가 된다.
		
		
		
	}
	
}

이전에 풀었던 방식과 유사하게 BFS를 이용해 풀었지만, 코드 자체가 많이 간결해졌다. 개념은 위와 동일하다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Dot{ // 좌표 저장 클래스
		int x;
		int y;
		
		public Dot(int x, int y) { 
			super();
			this.x = x;
			this.y = y;
		}
		
		public int getX() {
			return x;
		}
		public void setX(int x) {
			this.x = x;
		}
		public int getY() {
			return y;
		}
		public void setY(int y) {
			this.y = y;
		}				
}

class Main {
  
  	static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
    
    // BFS 메소드
	static void bfs(int[][] a, int[][] check, Dot d) {
		Queue<Dot> q = new LinkedList<>(); // BFS를 위한 큐 객체
				
		q.offer(d); // 초기 0,0 좌표를 큐에 삽입
		check[d.getX()][d.getY()] = 1; // 초기 출발 위치는 고정이며 1로 시작
		
		while(!q.isEmpty()) { // 주변에 1이 없을 때 까지 반복한다.
			Dot d_p = q.poll();
			int x = d_p.getX();
			int y = d_p.getY();
						
			for(int i=0;i<4;i++) { // 상, 하, 좌, 우 탐색 반복문
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx>=a.length || nx<0 || ny>=a[nx].length || ny < 0) continue;
				
				if(a[nx][ny] == 0) continue; // 0인 좌표는 무시한다.
				
                // 체크 배열에 초기화 된 값과 동일하면 방문하지 않았단 뜻이며, 그곳에 값이 1로 갈 수 있는 경로라면
				if( check[nx][ny] == Integer.MAX_VALUE && a[nx][ny] == 1){					
                	// 해당 체크 배열에 저장되어 있는 경로의 수와 현재 좌표에서 +1 했을 때의 경로의 수 중 최솟값을 저장
					check[nx][ny] = Math.min(check[x][y]+1,check[nx][ny]);
                    // 해당 좌표를 큐에 삽입 후 BFS 탐색 반복
					q.offer(new Dot(nx,ny));
				}
			}			
		}		
	}
	
	public static void main(String[] args)  {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt(); // 행
		int m = in.nextInt(); // 열
		
		int map[][] = new int[n][m]; // 데이터 저장 맵
		int check[][] = new int [n][m]; // 방문 여부 체크 배열
		
		for(int i =0;i<map.length;i++) { // 데이터 입력
			String str = in.next();
			for(int j =0;j<map[i].length;j++) {
				map[i][j] = str.charAt(j)-'0';
			}
		}
        
		for(int i =0;i<check.length;i++) { // int 형 체크 형 배열 초기화
        	// 최단 경로를 찾는 것이기 때문에 비교를 위해 초기값은 MAX_VALUE를 사용했다.
			Arrays.fill(check[i],Integer.MAX_VALUE);
		}
		
		Dot d = new Dot(0,0); // 초기 출발 위치 객체 생성
		bfs(map,check,d); // BFS 수행
		
		System.out.println(check[n-1][m-1]); // 마지막 도착지의 체크 배열에 저장되어 있는 최단 경로 출력
			
	  }
}

자바 미로찾기 최단거리 자바 미로찾기 스택 Java DFS 미로찾기 자바 BFS 문제 미로찾기 재귀함수 미로 탐색 알고리즘