Story of Jinuk Baek

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

개미가 부디칠 경우 통과한다고 보고 작성.,

속도는 O(n)

import java.util.Scanner;

public class P1852 {

	/**
	 * @param args
	 */

	public static void main(String[] args) {
		int testcase;
		Scanner scan = new Scanner(System.in);

		testcase = scan.nextInt();

		while (testcase– > 0)
		{
			int l = scan.nextInt();
			int n = scan.nextInt();

			int max = 0;
			int min = 0;

			for (int i=0; i<n; i++)
			{
				int t = scan.nextInt();

				max = Math.max(max, Math.max(l-t, t));
				min = Math.max(min, Math.min(l-t, t));
			}

			System.out.println(min + ” ” + max);
		}
	}
}