백준 - 3055 탈출(Java)

www.acmicpc.net/problem/3055

3055번: 탈출

 

1. 유형

- BFS

 

2. 설계

• s랑 *를 큐에 넣고시작
• 현재 좌표가 S일 경우 다음 값이 D이면 종료합니다.
• 현재 좌표가 S일경우 .으로만 움직입니다
• 현재가 *인 경우 다음 값이 . 이나 S로 움직입니다.

3. 풀이

4. 디버깅 실수

*인 경우, 즉 물이 한 좌표가 아니라 여러 좌표일 수 있습니다. 따라서 처음 입력값에서 ArrayList형식으로 좌표를 받아야 합니다. 이 점을 조심해야 합니다.

 

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

public class Main {
	static int R, C, res;
	static char map[][];
	static int dr[] = { -1, 1, 0, 0 };
	static int dc[] = { 0, 0, 1, -1 };
	static Queue<Pair> q;

	static class Pair {
		int r, c, cnt;

		Pair(int r, int c, int cnt) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		R = Integer.valueOf(st.nextToken());
		C = Integer.valueOf(st.nextToken());
		map = new char[R][C];
		q = new LinkedList<>();
		ArrayList<Pair> waterPos = new ArrayList<>();
		int start_r=0, start_c=0;
		for (int i = 0; i < R; i++) {
			String str = in.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
				if (map[i][j] == '*') {
					waterPos.add(new Pair(i,j,0));
				} else if (map[i][j] == 'S') {
					start_r = i;
					start_c = j;
				}
			}
		}
		res=0;
		q.add(new Pair(start_r, start_c, 0));
		for(Pair pos : waterPos) {
			q.add(pos);
		}
		bfs();
		if(res==0) {
			System.out.println("KAKTUS");
		}else
			System.out.println(res);
	}

	static void bfs() {
		while(!q.isEmpty()) {
			Pair cur =q.poll();
			for(int i=0; i<4; i++) {
				int nr = cur.r+dr[i];
				int nc = cur.c+dc[i];
				if(nr<0 || nc<0 || nr>=R || nc>=C || map[nr][nc]=='X') continue;
				if(map[cur.r][cur.c] == 'S' && map[nr][nc]=='D') {
					res = cur.cnt+1;
					return;
				}
				if(map[cur.r][cur.c] == 'S' && map[nr][nc]=='.') {
					map[nr][nc] = 'S';
					q.add(new Pair(nr,nc,cur.cnt+1));
				}
				if(map[cur.r][cur.c] == '*' && ((map[nr][nc]=='.') || (map[nr][nc]=='S'))) {
					map[nr][nc] = '*';
					q.add(new Pair(nr,nc,cur.cnt+1));
				}
			}
		}
	}
}