미로 최단거리

미로 최단거리 문제 – 프로그래밍 콘테스트 챌린징 책 P50 문제

너비 우선 탐색을 통해 문제를 풀음.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Save
{
	public int x;
	public int y;
	public int num;

	public Save(int x, int y, int num
	{
		this.x = x;
		this.y = y;
		this.num = num;
	}
}

public class Miro {

	public static void main(String[] args) {
		int x, y;
		int num = 0;
		int start_x = 0;
		int start_y = 0;
		int[][] arr = new int[102][102];
		Queue<Save> queue = new LinkedList<Save>();
		Scanner scan = new Scanner(System.in);

		x = scan.nextInt();
		y = scan.nextInt();

		for (int i = 0; i <= x + 1; i++) {
			for (int j = 0; j <= y + 1; j++)
			{
				arr[i][j] = -100;
			}
		}

		for (int i = 1; i <= x; i++)
		{
			char[] tmp = scan.next().toCharArray();

			for (int j = 0; j < y; j++)
			{
				if (tmp[j] == 'S')
				{
					start_x = i;
					start_y = j + 1;
				}
				else if (tmp[j] == '.')
				{
					arr[i][j + 1] = 0;
				}
				else if (tmp[j] == 'G')
				{
					arr[i][j + 1] = Integer.MAX_VALUE;
				}
			}
		}

		queue.add(new Save(start_x, start_y, num));

		while (!queue.isEmpty())
		{
			Save now = queue.poll();
			num = ++now.num;

			if (arr[now.x][now.y] == Integer.MAX_VALUE)
			{
				break;
			}

			arr[now.x][now.y] = now.num;

			if (arr[now.x - 1][now.y] == 0)
			{
				queue.add(new Save(now.x - 1, now.y, now.num));
			}
			if (arr[now.x][now.y - 1] == 0)
			{
				queue.add(new Save(now.x, now.y - 1, now.num));
			}
			if (arr[now.x + 1][now.y] == 0)
			{
				queue.add(new Save(now.x + 1, now.y, now.num));
			}
			if (arr[now.x][now.y + 1] == 0)
			{
				queue.add(new Save(now.x, now.y + 1, now.num));
			}
		}
		System.out.println(num);
	}
}