[JAVA 자바] 백준 2179번 : 미로 탐색

▶ 문제

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

2178번: 미로 탐색

 

▶ 설명

갈림길 없이 일직선으로 되어 있는 미로라면 DFS, BFS로 이동 거리를 구할 수 있지만

 갈림길이 있는 미로라면 BFS로만 최소 이동 거리를 구할 수 있다.

문제의 예제를 살펴보면 1로 된 곳은 지나갈 수 있지만 0은 지나갈 수 없는 조건이 주어졌다.

그럼 출발선인 1,1부터 살펴보자.

 

 

내부적으로 2차 배열로 만들 것이기 때문에 처음 시작하는 곳은 0,0 라고 할 수 있다.

먼저, [0,0] 에서 갈 수 있는 칸이 어디인지를 살펴본다.

왼쪽과 위는 막혀있기 때문에 오른쪽과 아래로 탐색할 수 있다. 

하지만 오른쪽 칸은 0이기 때문에 그 쪽으로 갈 수 없고, 결국 아래칸[1,0] 으로만 이동이 가능하다.

탐색한 곳에 기존 칸의 값이었던 1에서 1을 더해주어 2라는 값을 주도록 한다.

 

 

 

 

 

 

그다음 [1,0] 을 방문하여 또다시 위에서처럼 방문할 수 있는 칸을 위,아래,좌,우를 탐색해본다.

왼쪽은 막혀있어서 위,아래,오른쪽을 탐색 후보로 올릴 수 있다. 

하지만 위칸은 이미 방문한 노드이고, 오른쪽은 0의 값을 가지므로 방문할 수가 없다. 

 

 

 

 

 

그다음 노드도 마찬가지이다.

index 범위가 넘어가거나 (미로 판 바깥), 0이면 탐색 후보로 제외시키도록 하고,

1인 값을 가진 노드라면 그 칸에 지나온 개수를 1씩 더해주면 되는 것이다.

 

 

 

 

더이상 탐색할 후보로 올릴 칸이 없다면 마지막 값인 15를 출력하기만 하면 된다.

 

자료구조 Queue의 특징이 잘 묻어난 문제였다.

방문할 칸들을 Queue에 담을 때 쌍으로 되어 있는 2차 배열의 index가 들어가게 된다.

그 형태를 객체로 할지, 배열로 할지에 따라서 두 개의 풀이로 작성해 보았다.

 

 

 

▶ 문제 풀이

🌱 풀이1. Queue에 담기는 데이터의 유형을 객체로 하기

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

public class Main {
	static int[][] graph;
	static int n, m;

	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()); // row
		m = Integer.parseInt(st.nextToken()); // column

		graph = new int[n][m];
		
        // 0과 1의 값을 갖는 2차 배열 만들기
		for (int i = 0; i < graph.length; i++) {
			String s = br.readLine();
			for (int j = 0; j < graph[i].length; j++) {
				graph[i][j] = s.charAt(j) - '0';
			}
		}

		bfs(0, 0);
		
        //마지막 배열의 index 값 출력
		System.out.println(graph[n - 1][m - 1]);
	}

	private static void bfs(int x, int y) {
		int[] aroundX = { 0, 0, -1, 1 }; // 위아래, 세로로 이동하며 탐색
		int[] aroundY = { -1, 1, 0, 0 }; // 좌우, 가로로 이동하며 탐색
		
        //XyNode라는 객체 형태로 Queue에서 다루기.
		LinkedList<XyNode> q = new LinkedList<>();
        //첫 방문 노드를 Queue에 담기.
		q.offer(new XyNode(x, y));

		while (!q.isEmpty()) {
        	//Queue의 front에 있는 데이터를 꺼내서 변수x,y에 index를 담기.
			XyNode node = q.poll();
			x = node.getX();
			y = node.getY();
            
            //위,아래,좌,우칸의 인덱스로 만들어 방문 가능한 곳인지 탐색하기.
			for (int i = 0; i < 4; i++) {
				int newX = x + aroundX[i];
				int newY = y + aroundY[i];
				
                //배열 범위를 벗어나는 index의 경우 무시하기
				if (newX >= n || newX < 0 || newY >= m || newY < 0) {
					continue;
				}
                
                //값이 1인 곳에 1을 더해주고, Queue에 index를 넣어주기.
				if (graph[newX][newY] == 1) {
					graph[newX][newY] = graph[x][y] + 1;
					q.offer(new XyNode(newX, newY));

				}
			}
		}

	}

}

class XyNode {
	private int x;
	private int y;

	public XyNode(int x, int y) {
		this.x = x;
		this.y = y;
	}
	//조회만 할 것이기 때문에 getter만 생성.
	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}

	@Override
	public String toString() {
		return "XyNode [x=" + x + ", y=" + y + "]";
	}

}

🌱 풀이2. Queue에 담기는 데이터의 유형을 배열로 하기

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

public class Main {
	static int[][] graph;
	static int n, m;

	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()); // row
		m = Integer.parseInt(st.nextToken()); // column

		graph = new int[n][m];

		// 0과 1 입력받기.
		for (int i = 0; i < graph.length; i++) {
			String s = br.readLine();
			for (int j = 0; j < graph[i].length; j++) {
				graph[i][j] = s.charAt(j) - '0';
			}
		}

		bfs(0, 0);

		System.out.println(graph[n - 1][m - 1]);
	}

	private static void bfs(int x, int y) {
		int[] aX = { 0, 0, -1, 1 }; // around X. 위아래, 세로로 이동하며 탐색
		int[] aY = { -1, 1, 0, 0 }; // around Y. 좌우, 가로로 이동하며 탐색

		LinkedList<int[]> q = new LinkedList<>();
		q.offer(new int[] { x, y });

		while (!q.isEmpty()) {
			int[] node = q.poll();
			x = node[0];
			y = node[1];
			for (int i = 0; i < 4; i++) {
				int newX = x + aX[i];
				int newY = y + aY[i];

				if (newX >= n || newX < 0 || newY >= m || newY < 0) {
					continue;
				}
				if (graph[newX][newY] == 1) {
					graph[newX][newY] = graph[x][y] + 1;
					q.offer(new int[] { newX, newY });

				}
			}
		}

	}

}

Queue에 offer(담기)하거나 poll(빼기) 할 때에 new int[] {x,x} 로 한다는 것만 위의 첫번째 풀이와 다르고, 그 이외에는 모두 같다.