본문 바로가기
개발/코딩테스트

백준 2178번: 미로 탐색 [JAVA]

by 로또 2023. 3. 18.

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

 

2178번: 미로 탐색

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

www.acmicpc.net

  • 풀이

최단 경로를 찾는 문제이므로 BFS를 사용하면 된다.

 

1. 입력

각각의 수가 붙어서 입력으로 주어지므로 분리 시켜줘야 한다.

for (int i=0; i<N; i++) {
		int line = Integer.parseInt(bf.readLine());
		for (int j=0; j<M; j++) {
		arr[i][j] = line/(int)(Math.pow(10, M-j-1));
		line%=(int)(Math.pow(10, M-j-1));
}

처음에는 이렇게 10의 제곱을 이용한 몫으로 구분을 해주었지만, M의 범위가 100까지이기 때문에 line이 너무 큰 수가 되어 정수형 타입에 담지 못 하는 오류가 났다.

// 입력
for (int i=0; i<N; i++) {
	String s = bf.readLine();
	for (int j=0; j<M; j++) {
		arr[i][j] = (int)s.charAt(j)-48;
	}
}

따라서 이렇게 String으로 받아 charAt으로 분할해준 뒤 int로 형변환해서 읽었다.

문자열 ‘0’은 int로 변환했을 때 48이 되고 문자열 ‘1’은 int로 변환했을 때 49가 되므로 -48 시켜주었다.

 

2. BFS

좌표를 큐에 담는 방법이 고민이었는데, 좌표 클래스를 만들어서 큐에 넣어주면 된다고 한다.

따라서 이렇게 Pair라는 클래스를 만들어주었다.

static class Pair{
		int x, y, level;
		Pair(int x, int y, int level){
			this.x = x;
			this.y = y;
			this.level = level;
		}
}

x, y는 좌표를 뜻하고, level은 시작점부터 이 점까지의 최단 거리를 담은 변수이다.

while문은 시작점부터 시작해서 (N,M)을 찾을 때까지 반복되는데, 기본적인 BFS 형태와 동일하지만 인접한 노드를 큐에 넣을 때 level을 1씩 증가시켜서 거리를 기록하였다는 차이가 있다.

static void BFS(int startX, int startY) {
		Queue <Pair> que = new ArrayDeque<>();
		
		// 시작점 Enqueue
		Pair start = new Pair(startX, startY, 1);
		que.add(start);
		isVisited[startX][startY] = true;
	
		while(!que.isEmpty()) {
			Pair now = que.poll();
			
			for (int i=0; i<4; i++) { // 기준점 상하좌우 탐색
				Pair next = new Pair(now.x + dx[i], now.y + dy[i], now.level+1);

				// 범위 벗어나면 X
				if (next.x >= N || next.x < 0 || next.y < 0 || next.y>=M) continue; 
				// 길이 아니면 X
				if (arr[next.x][next.y]==0) continue;
				// 이미 방문했으면 X
				if (isVisited[next.x][next.y]) continue;
				// 종점이면 종료
				if (next.x == N-1 && next.y == M-1) {
					System.out.println(next.level);
					return;
				}

				// Enqueue
				que.add(next);
				isVisited[next.x][next.y] = true;
			}
		}
	}

 

전체코드

더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int arr[][];
	static int cnt;
	static int [] dx = {-1,1,0,0}; // 상하좌우
	static int [] dy = {0,0,-1,1};
	static boolean [][] isVisited;
	
	static class Pair{
		int x, y, level;
		Pair(int x, int y, int level){
			this.x = x;
			this.y = y;
			this.level = level;
		}
	}
	
	static void BFS(int startX, int startY) {
		Queue <Pair> que = new ArrayDeque<>();
		
		// 시작점 Enqueue
		Pair start = new Pair(startX, startY, 1);
		que.add(start);
		isVisited[startX][startY] = true;
	
		while(!que.isEmpty()) {
			Pair now = que.poll();
			
			for (int i=0; i<4; i++) { // 기준점 상하좌우 탐색
				Pair next = new Pair(now.x + dx[i], now.y + dy[i], now.level+1);

				// 범위 벗어나면 X
				if (next.x >= N || next.x < 0 || next.y < 0 || next.y>=M) continue; 
				// 길이 아니면 X
				if (arr[next.x][next.y]==0) continue;
				// 이미 방문했으면 X
				if (isVisited[next.x][next.y]) continue;
				// 종점이면 종료
				if (next.x == N-1 && next.y == M-1) {
					System.out.println(next.level);
					return;
				}

				// Enqueue
				que.add(next);
				isVisited[next.x][next.y] = true;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int [N][M];
		isVisited = new boolean [N][M];
		
		// 입력
		for (int i=0; i<N; i++) {
			String s = bf.readLine();
			for (int j=0; j<M; j++) {
				arr[i][j] = (int)s.charAt(j)-48;
			}
		}
		
		// 경로 찾기
		BFS(0,0);
		
	}
}

댓글