[JAVA]BOJ(백준) - 미로 탐색

- 문제 내용

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

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

www.acmicpc.net

- 문제 접근 방법

가장먼저 모두 탐색하는 것이 아니라 최소의 칸수 즉, 최단 거리를 구하는 문제라 BFS 방식을 쓰는것으로 생각했다.

그리고 다른 DFS 문제와 마찬가지로 상하좌우를 탐색하는데 인접한 모든 값들을 살핀다.

또 미로의 값을 하나씩 탐색할때마다 이전값+1을 해줌으로써 한단계씩 넘어갈 때 마다 값을 증가시킨다.

가장 시간이 많이 걸렸던 점은 그래프의 경우 노드를 큐에 넣고 빼고를 반복하면 되는데 이건 다음 값의 위치를 넣기위해선 그 값의 인덱스를 큐에 저장하고 있어야 한다는 점이였다.

도저히 어떻게 저장해야할지 모르겠어서 다른 분들의 많은 풀이를 참고했다.

종합해보니 2가지의 방법으로 풀수 있었다.

인덱스를 저장하는 클래스를 만들어서 큐에 객체를 넣는 방식.
x 인덱스를 저장하는 큐, y 인덱를 저장하는 큐 -> 이렇게 2개 만드는 방식.

위의 두가지 방법은 bfs 알고리즘이 맞지만 개인적으로 첫번째가 bfs 방식에 더 어울린다 생각한다.

하지만 두번째 방법도 쉽게 할수 있고 알아보기 쉽기 때문에 알아두면 좋을것 같다.

아래 풀이는 첫번째 방법의 경우 main, bfs, xy클래스, 전체코드로 나눠서 올렸고

두번째 방법은 그냥 한번에 올렸다.

- 풀이(첫번째 방법)

Main( 첫번째 두번째 방법 모두 동일)

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		check = new boolean[N][M];
		miroMap = new int[N][M];
		
		for(int i=0; i<N; i++) {
			num = br.readLine();
			for(int j=0; j<M; j++) {
				miroMap[i][j] = Integer.parseInt(num.substring(j, j+1));  
			}
		}
		
		new BOJ_2178_2().bfs(0, 0);
	}

입력값( 첫번째 두번째 방법 모두 동일)

public class BOJ_2178 {
	static int N; // 행 = 세로크기
	static int M; // 열 = 가로크기
	static String num; // 입력받는 0,1 숫자들
	static boolean[][] check; // 방문배열
	static int[][] miroMap; // 미로지도
	
	static int[] x = {0, 0, -1, 1}; //상하좌우
	static int[] y = {-1, 1, 0, 0}; //상하좌우

BFS(첫번째 방법)

public void bfs(int v1, int v2) {
		Queue<xy> queue = new LinkedList<xy>(); // 제네릭은 xy객체 넣을거라서 xy로.
		check[v1][v2] = true; // 방문처리
		queue.add(new xy(v1,v2)); // 객체생성과 동시에 큐에 넣어서 인덱스 저장.
		
		while(!queue.isEmpty()) {
			xy xy = queue.poll(); // 큐에서 객체반환 받고 소멸시킴.
			int nowX = xy.x1; // miroMap에서 현재 가리키는 위치의 인덱스 x를 저장
			int nowY = xy.y1; // y를 저장
			
			for(int i=0; i<4; i++) { // 상하좌우 4번 탐색하면서 조건에 맞는거 전부 큐에 저장
				int dx = nowX + x[i]; // 다음 인덱스 x를 -,+ 해서 저장
				int dy = nowY + y[i]; // 다음 인덱스 y를 -,+ 해서 저장
				
				if(dx>=0 && dy>=0 && dx<N && dy<M) {
					if(miroMap[dx][dy]==1 && !check[dx][dy]) {
						queue.add(new xy(dx,dy)); // 큐에 다음 위치의 인덱스들을 객체로 저장 
						miroMap[dx][dy] = miroMap[nowX][nowY]+1; //미로의 현재위치값에 1씩 더하면서 다음 위치 값을 할당함.
						check[dx][dy]=true; //다음 위치 탐색완료.(상하좌우 중 하나)
					}//if
				}//if
			}//for
		}//while
		System.out.println(miroMap[N-1][M-1]); //N,M은 크기라서 인덱스에 맞게 -1을 해줌
	}//bfs

참고로 bfs 함수에서 상하좌우의 for문을 돌때 if문에 dx<M , dy<N 을 쓰면 에러가 난다. 이유는 N,M은 행렬인데 다른말로 N,M은 가로세로 크기라고 생각을 했을때 dx는 행(세로크기)이 바뀌는것 , dy은 열(가로크기)이 바뀌는것이기 때문이다.

xy 클래스(첫번째 방법)

class xy{ //큐에 넣을 객체 클래스로 만듦.
	int x1;
	int y1;
	
	public xy(int v1, int v2) { //생성자
		this.x1 = v1;
		this.y1 = v2;
	}
}

첫번째 방법 전체 코드

package org.boj.dfs.bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class BOJ_2178 {
	static int N; // 행 = 세로크기
	static int M; // 열 = 가로크기
	static String num; // 입력받는 0,1 숫자들
	static boolean[][] check; // 방문배열
	static int[][] miroMap; // 미로지도
	
	static int[] x = {0, 0, -1, 1}; //상하좌우
	static int[] y = {-1, 1, 0, 0}; //상하좌우
	
	public void bfs(int v1, int v2) {
		Queue<xy> queue = new LinkedList<xy>(); // 제네릭은 xy객체 넣을거라서 xy로.
		check[v1][v2] = true; // 방문처리
		queue.add(new xy(v1,v2)); // 객체 자체를 넣어서 인덱스 저장.
		
		while(!queue.isEmpty()) {
			xy xy = queue.poll(); // 큐에서 객체반환 받고 소멸시킴.
			int nowX = xy.x1; // miroMap에서 현재 가리키는 위치의 인덱스 x를 저장
			int nowY = xy.y1; // y를 저장
			
			for(int i=0; i<4; i++) { // 상하좌우 4번 탐색하면서 조건에 맞는거 전부 큐에 저장
				int dx = nowX + x[i]; // 다음 인덱스 x를 -,+ 해서 저장
				int dy = nowY + y[i]; // 다음 인덱스 y를 -,+ 해서 저장
				
				if(dx>=0 && dy>=0 && dx<N && dy<M) {
					if(miroMap[dx][dy]==1 && !check[dx][dy]) {
						queue.add(new xy(dx,dy)); // 큐에 다음 위치의 인덱스들을 객체로 저장 
						miroMap[dx][dy] = miroMap[nowX][nowY]+1; //미로의 현재위치값에 1씩 더하면서 다음 위치 값을 할당함.
						check[dx][dy]=true; //다음 위치 탐색완료.(상하좌우 중 하나)
					}//if
				}//if
			}//for
		}//while
		System.out.println(miroMap[N-1][M-1]); //N,M은 크기라서 인덱스에 맞게 -1을 해줌
	}//bfs
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		check = new boolean[N][M];
		miroMap = new int[N][M];
		
		for(int i=0; i<N; i++) {
			num = br.readLine();
			for(int j=0; j<M; j++) {
				miroMap[i][j] = Integer.parseInt(num.substring(j, j+1));  
			}
		}
		
		new BOJ_2178().bfs(0, 0);
	}
}

class xy{ //큐에 넣을 객체 클래스로 만듦.
	int x1;
	int y1;
	
	public xy(int v1, int v2) { //생성자
		this.x1 = v1;
		this.y1 = v2;
	}
}

두번째 방법 전체 코드

package org.boj.dfs.bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class BOJ_2178_2 {
	static int N; // 행 = 세로크기
	static int M; // 열 = 가로크기
	static String num; // 입력받는 0,1 숫자들
	static boolean[][] check; // 방문배열
	static int[][] miroMap; // 미로지도
	
	static int[] x = {0, 0, -1, 1}; //상하좌우
	static int[] y = {-1, 1, 0, 0}; //상하좌우
	
	public void bfs(int v1, int v2) {
		Queue<Integer> queue_x = new LinkedList<Integer>(); // x인덱스 저장할 큐
		Queue<Integer> queue_y = new LinkedList<Integer>(); // y인덱스 저장할 큐 
		check[v1][v2] = true; // 방문처리
		queue_x.add(v1);
		queue_y.add(v2);
		
		while(!queue_x.isEmpty()) {
			int nowX = queue_x.poll();
			int nowY = queue_y.poll();
			
			for(int i=0; i<4; i++) { // 상하좌우 4번 탐색하면서 조건에 맞는거 전부 큐에 저장
				int dx = nowX + x[i]; // 다음 인덱스 x를 -,+ 해서 저장
				int dy = nowY + y[i]; // 다음 인덱스 y를 -,+ 해서 저장
				
				if(dx>=0 && dy>=0 && dx<N && dy<M) {
					if(miroMap[dx][dy]==1 && !check[dx][dy]) {
						queue_x.add(dx); // 다음 x인덱스 저장
						queue_y.add(dy); // 다음 y인덱스 저장
						miroMap[dx][dy] = miroMap[nowX][nowY]+1; //미로의 현재위치값에 1씩 더하면서 다음 위치 값을 할당함.
						check[dx][dy]=true; //다음 위치 탐색완료.(상하좌우 중 하나)
					}//if
				}//if
			}//for
		}//while
		System.out.println(miroMap[N-1][M-1]); //N,M은 크기라서 인덱스에 맞게 -1을 해줌
	}//bfs
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		check = new boolean[N][M];
		miroMap = new int[N][M];
		
		for(int i=0; i<N; i++) {
			num = br.readLine();
			for(int j=0; j<M; j++) {
				miroMap[i][j] = Integer.parseInt(num.substring(j, j+1));  
			}
		}
		
		new BOJ_2178_2().bfs(0, 0);
	}
}

- 마치며

이번 문제에서 가장 어려웠던 부분은 큐에 값을 어떻게 넣을것인가에 대한 것이였다. 알고리즘에서 클래스를 만들어 객체를 넣는다는 생각은 못했는데 좋은 방식이라고 생각한다.

'알고리즘 > BOJ' 카테고리의 다른 글

[JVAV] BOJ(백준) - 토마토 - 7569 (0)	2021.10.25
[JAVA] BOJ(백준) - 토마토 - 7576 (0)	2021.10.25
[JAVA]BOJ(백준) - 유기농 배추 - 1012 (0)	2021.10.19
[JAVA]BOJ(백준) - 단지번호붙이기 - 2667 (0)	2021.10.19
[JAVA]BOJ(백준) - 바이러스 - 2606 (0)	2021.10.08

기억하려면 기록해라

[JAVA]BOJ(백준) - 미로 탐색 - 2178

- 문제 내용

- 문제 접근 방법

- 풀이(첫번째 방법)

- 마치며

'알고리즘 > BOJ' 카테고리의 다른 글

티스토리툴바

[JAVA]BOJ(백준) - 미로 탐색 - 2178

- 문제 내용

- 문제 접근 방법

- 풀이(첫번째 방법)

- 마치며

'알고리즘 > BOJ' 카테고리의 다른 글

'알고리즘/BOJ' Related Articles

티스토리툴바