[SWEA SW Expert Academy] 1249 보급로

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE

SW Expert Academy

 

출발지점에서 도착지점까지 최소의 비용을 사용하는 경로를 찾아 내는 문제이다.

BFS를 이용해서 경로를 찾는 방식으로 경로를 찾는 방식을 택했다.

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

public class SWEA_1249_보급로 {
	private static class Point {
		int x, y;

		public Point(int x, int y) {	//좌표를 저장한다.
			super();
			this.x = x;
			this.y = y;
		}

	}

	private static int dx[] = { -1, 1, 0, 0 };
	private static int dy[] = { 0, 0, -1, 1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int T = Integer.parseInt(st.nextToken());
		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(bf.readLine());
			int N = Integer.parseInt(st.nextToken());
			int arr[][] = new int[N][N];
			int visit[][] = new int[N][N];		//방문체크를 해줄 배열
			for (int i = 0; i < N; i++) {
				String temp = bf.readLine();
				for (int j = 0; j < N; j++) {
					arr[i][j] = temp.charAt(j) - '0';
					visit[i][j] = Integer.MAX_VALUE;		//방문체크 배열을 최대값으로 초기화
				}
			}
			visit[0][0] = 0;		//시작지점을 0으로 만들어준다.
			LinkedList<Point> que = new LinkedList<Point>();
			que.add(new Point(0, 0));
			while (!que.isEmpty()) {		//BFS를 이용한 완전 탐색
				Point point = que.poll();
				for (int k = 0; k < 4; k++) {	//4방탐색을 통해 최소가 되는 곳을 찾는다.
					int x = point.x + dx[k];
					int y = point.y + dy[k];
					if (x >= 0 && x < N && y >= 0 && y < N && 	//배열안에 있는지 체크
                    visit[point.x][point.y] + arr[x][y] < visit[x][y]) {	//다음지역으로 갈 경우, visit에 저장된 값보다 작으면 리스트에 저장해준다.
						visit[x][y] = visit[point.x][point.y] + arr[x][y];
						que.add(new Point(x, y));
					}
				}
			}
			System.out.println("#" + t + " " + visit[N - 1][N - 1]); //마지막에 visit에 최소값이 들어가게 된다.

		}
	}
}