백준 - 2178번 - 미로

이상훈·2023년 4월 30일
0

2178번

import java.util.*;
import java.io.*;

public class Main{

	static class Miro {
		int x;
		int y;
		int moved;

		public Miro(int x, int y, int moved) {
			this.x = x;
			this.y = y;
			this.moved = moved;
		}
	}

	static int[][] graph;
	static int m, n;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st  = new StringTokenizer(bf.readLine());
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());

		graph = new int[m+1][n+1];

		for (int i = 1; i<m+1; i++) {
			String input = bf.readLine();
			for (int j = 0; j<n; j++) {
				graph[i][j+1] = input.charAt(j)-'0';
			}
		}

		System.out.println(bfs());
	}

	static int bfs() {
		Queue<Miro> queue = new LinkedList<>();
		int moved = 0;
		
		queue.add(new Miro(1, 1, 1));

		while (!queue.isEmpty()) {
			Miro miro = queue.poll();
			moved = miro.moved;

			for (int i = 0; i<4; i++) {
				int nx = miro.x + dx[i];
				int ny = miro.y + dy[i];
				if (nx > 0 && ny > 0 && nx <= m && ny <= n) {

					if (graph[nx][ny] == 1) {
						graph[nx][ny] = 0;
						queue.add(new Miro(nx, ny, moved+1));
						if (nx == m && ny == n) {
							return moved+1;
						}
					}
				}
			}
		}

		return moved;
	}
}

풀이


0과 1로 입력된 2차원 배열이 있다. 1,1부터 m,n까지 1로 이어진 최단 거리를 구하는 문제다.

miro 클래스를 자료형으로 하는 큐를 선언한다.
1, 1을 큐에 넣어주고 bfs탐색을 시작한다. 만약 가로 세로 위 아래에 1이 나오면 0으로 만들어주고 moved를 +1 해서 큐에 저장한다.

이 과정을 반복해서 m, n에 도달하면 moved를 리턴하게 해주었다.

if (nx == m && ny == n) {
	return moved+1;
}

처음에 이 조건을 넣어주지 않아서 최단 거리를 계산하지 않고 최장거리를 계산해서 출력해줬다.

0개의 댓글