[SWEA / JAVA] 10966 물놀이를 가자.

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXWXMZta-PsDFAST

SW Expert Academy

 

문제 풀이

문제의 유형은 BFS로 보였다. DP를 이용하면 더 시간 복잡도를 줄일 수 있을 것처럼 보인다.

2차원 배열에 물의 위치를 기준으로 땅까지의 거리가 얼마나 되는가를 알아내서 넣어주면 될것 같다.

 

1. 물의 위치를 큐에 넣는다.
2. BFS로 돌려서 최소거리를 해당 배열 위치에 넣어준다.

 

소스코드

import java.util.*;

class Pair {
	int x;
	int y;
	int d;

	public Pair(int x, int y, int d) {
		super();
		this.x = x;
		this.y = y;
		this.d = d;
	}
}

public class Solution {


	static int [] dx = {0,1,0,-1};
	static int [] dy=  {1,0,-1,0};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++) {
			int N =sc.nextInt();
			int M =sc.nextInt();
			int [][] grd = new int[N][M];
			int answer= 0;
			for (int[] is : grd) Arrays.fill(is, 999);
			Queue<Pair> que = new LinkedList<Pair>();

			for (int i = 0; i < N; i++) {
				String row = sc.next();
				for (int j = 0; j < M; j++) {
					if(row.charAt(j) =='W')	{
						grd[i][j] = 0;
						que.add(new Pair(i,j,0));
					}
				}
			}

			while(!que.isEmpty()) {

				Pair p = que.poll();

				for(int way= 0; way<4 ; way++) {

					int nextX = p.x +dx[way];
					int nextY = p.y +dy[way];

					if(nextX<0 || nextY<0 || nextX>=N || nextY>=M) continue;

					if(grd[nextX][nextY] > (p.d+1)) {
						grd[nextX][nextY] = (p.d+1);
						que.add(new Pair(nextX, nextY,p.d+1));
					}
				}
			}

			for (int[] is : grd) {
				for (int val : is) {
					answer += val;
//					System.out.print(" " + val);
				}
//				System.out.println();
			}

			System.out.println("#"+test_case+" "+answer);
		}
	}
}