Baekjoon 16441 아기돼지와 늑대 JAVA

16441번: 아기돼지와 늑대

문제

산으로 둘러싸인 고리분지에 사는 아기돼지 삼형제는 엄마돼지로부터 독립하여 새 집을 지으려 합니다.

고리분지는 N × M 크기의 2차원 격자로 나타낼 수 있고 각 칸의 지형은 초원, 빙판, 산 중 하나입니다.

고리분지에는 돼지가족들 뿐만 아니라 늑대들도 살고 있습니다. 늑대는 상하좌우 인접한 칸 중 산이 아닌 칸으로 이동할 수 있습니다. 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다.

게으른 아기돼지들은 지푸라기로 집을 지을 예정이기 때문에 늑대가 집이 있는 칸에 도착하기만 한다면 손쉽게 침입할 수 있습니다. 고리분지에 사는 늑대들이 도달할 수 없고 지형이 초원인 칸을 '안전한 곳'이라고 부릅니다. 게으른 아기돼지들을 위해 고리분지의 지도가 주어지면 지도 위에 모든 안전한 곳의 위치를 표시해주세요.

 

입력

첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열들이 주어집니다. 

i+1번째 줄의 j번째 문자는 i번째 행 j번째 열의 지형 종류를 의미하며 '.' 일 경우 초원, '+' 일 경우 빙판, '#' 일 경우 산, 그리고 'W'는 늑대가 살고 있음을 나타냅니다. 늑대가 사는 칸은 여러 개일 수 있고 늑대가 사는 지형은 항상 초원입니다. 지도의 첫 번째, N번째 행과 첫 번째, M번째 열은 항상 산입니다.

출력

입력으로 주어진 지도를 출력하되 아기돼지가 살 수 있는 초원은 문자 'P'로 대체하여 출력합니다.

풀이

코드 참고

코드

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()), m=Integer.parseInt(st.nextToken());
		char [][] map = new char [n][m];
		boolean [][] pigs = new boolean [n][m], isVisited = new boolean[n][m];	// pigs배열은 가능성이 있는 위치를 true로 설정
		Queue<int[]> q = new LinkedList<int[]>();
		for(int i=0;i<n;i++) {
			String str = br.readLine();
			for(int j=0;j<m;j++) {
				map[i][j]=str.charAt(j);
				if(map[i][j]=='W')
					q.add(new int[] {i,j});
				else if(map[i][j]=='.')
					pigs[i][j]=true;
			}
		}
		int [] dx = {-1,1,0,0}, dy= {0,0,1,-1};
		while(q.size()>0) {
			int [] cur = q.poll();
			int x=cur[0], y=cur[1];
			isVisited[x][y]=true;
			
			for(int i=0;i<4;i++) {
				if(x+dx[i]>=0 && x+dx[i]<n && y+dy[i]>=0 && y+dy[i]<m) {
					// 산이라서 탐색 불가능
					if(map[x+dx[i]][y+dy[i]]=='#')
						continue;
					// 초원이거나 늑대가 있는 자리거나, 동시에 한번도 방문하지 않은 위치면 탐색
					else if((map[x+dx[i]][y+dy[i]]=='.' || map[x+dx[i]][y+dy[i]]=='W') && !isVisited[x+dx[i]][y+dy[i]]) {
						q.add(new int[] {x+dx[i], y+dy[i]});
						isVisited[x+dx[i]][y+dy[i]]=true;
						pigs[x+dx[i]][y+dy[i]]=false;	// 만약 초원이었다면 늑대가 탐색 가능한 지역이기에 돼지는 살지 못함
					}
					else if(map[x+dx[i]][y+dy[i]]=='+') {	// 빙판이라면 미끄러져서 산에 막히거나 초원까지 가야함
						int j=1;
						while(map[x+dx[i]*j][y+dy[i]*j]=='+') {	// 미끄러지기
							j++;
						}
						// 미끄러지기가 끝난 상태는 벽에 막혀서 끝나거나 초원에 도착한 경우임
						
						// 벽에 막힌 상태   W+++# 위아래로 움직일 수 있음
						// 미끄러져서 도착했다면 그 위치로부터 지나온 방향에 수직으로 탐색이 다시 가능
						// 현재 위치는 얼음이 끝난 다음 위치이기에 이동방향을 한칸 뒤로가서 큐에 삽입
						if(map[x+dx[i]*j][y+dy[i]*j]=='#' && !isVisited[x+dx[i]*(j-1)][y+dy[i]*(j-1)]) {
							q.add(new int[] {x+dx[i]*(j-1), y+dy[i]*(j-1)});
							isVisited[x+dx[i]*(j-1)][y+dy[i]*(j-1)]=true;
						}
						// 다 미끄러지고 초원  W+++. 초원부터 움직임
						// 얼음에 다 미끄러지고 초원에 도착했기에 4방탐색이 가능해짐
						// 동시에 늑대가 탐색을 했기에 돼지는 거주불가능
						if(map[x+dx[i]*j][y+dy[i]*j]=='.' && !isVisited[x+dx[i]*j][y+dy[i]*j]) {
							q.add(new int[] {x+dx[i]*j, y+dy[i]*j});
							isVisited[x+dx[i]*j][y+dy[i]*j]=true;
							pigs[x+dx[i]*j][y+dy[i]*j]=false;
						}
					}
				}
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(pigs[i][j])	// 처음에 초원 위치에서 늑대가 탐색하지 않은 경로라면 P를 출력
					bw.write('P');
				else
					bw.write(map[i][j]);
			}
			bw.write("\n");
		}
		bw.close();
	}
}