[SWExpert][10966][D4] 물놀이를 가자

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXWXMZta-PsDFAST&categoryId=AXWXMZta-PsDFAST&categoryType=CODE&problemTitle=%EB%AC%BC%EB%86%80%EC%9D%B4&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

문제풀이

정형적인 BFS 문제이다. 그러나 막상 보자마자 쉽다고 간단하게 땅과 물의 list를 만들어 2중 포문으로 돌렸지만 최악의 경우 NxM이 1000x1000이고 100만 2차원 배열에서 땅의 개수가 50만이 되고 물의 개수도 50만 일 때 50만 x50 만이 되어 버린다.

 

또 다른 경우는 땅 위치를 List에 담아서 물의 위치를 찾을때까지 BFS 하는 경우인데 이 경우도 시간 초과가 뜬다.

그래서 물의 위치를 List에 담고 초기 위치들을 Queue에 넣어서 BFS를 돌려 자기(물)의 영역을 만든다

visited가 true인 경우 이미 방문하였기 때문에 check배열에 땅의 자리는 최솟값을 가지고 있다.

 

Queue가 빌때까지 반복문을 돌려서 check배열에 있는 값들을 다 더하면 최솟값들의 합이다.

코드

import java.util.*;
import java.io.*;

public class solution {
	static int N, M, min;
	static int map[][];
	static List<Pos> list;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };
	static int check[][];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			check = new int[N][M];
			list = new ArrayList<>();
			min =0;
			
			//초기화
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					check[i][j] = Integer.MAX_VALUE;
				}
			}


			for (int i = 0; i < N; i++) {
				String a = br.readLine();

				for (int j = 0; j < M; j++) {
					//구하게 쉽게 하기 위해 따로 정의
					if ('L' == a.charAt(j)) {
						map[i][j] = 1;
					} else {
						list.add(new Pos(i, j));
						map[i][j] = 0;
					}
				}
			}

			bfs();
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					// max인 경우 물의 위치
					if(check[i][j] == Integer.MAX_VALUE) continue;
					min += check[i][j];
				}
			}
			
			System.out.println("#"+tc+" "+min);
		}
	}

	private static void bfs() {
		Queue<Pos> qu = new LinkedList<>();
		boolean[][] visited = new boolean[N][M];
		
		// 초기 물의 위치 넣기
		for (int i = 0; i < list.size(); i++) {
			Pos p = list.get(i);
			qu.offer(p);
			visited[p.x][p.y] = true;
		}
		
		int index =1;

		while (!qu.isEmpty()) {
			int size = qu.size();

			for (int i = 0; i < size; i++) {
				Pos pos = qu.poll();
				for (int k = 0; k < 4; k++) {
					int x = pos.x + dx[k];
					int y = pos.y + dy[k];
					
					//범위를 벗어나거나 이미 방문한 경우, 또는 물의 위치인경우
					if (x < 0 || x >= N || y < 0 || y >= M || visited[x][y] || map[x][y] == 0)
						continue;
					
					// 땅을 만나면 check배열에 영역 표시
					if (map[x][y] == 1) {
						check[x][y] = index;
					}
					
					visited[x][y] = true;
					qu.add(new Pos(x,y));
				}
				
			}
			index++;
		}
	}
	

	static class Pos{
		int x;
		int y;
		
		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}