미로 최단거리 문제 – 프로그래밍 콘테스트 챌린징 책 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);
}
}
About the Author
