문제 바로가기
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님 블로그에서 힌트를 얻을 수 있었다. 혹시라도 막히는 분들은 참고하시면 좋을 것 같다.
//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]); // 마지막 도착지의 체크 배열에 저장되어 있는 최단 경로 출력 } }