[백준-java] 불! 4179번

알고리즘 : BFS

 

이번에 2024년도 하반기 삼성전자 코테에서도 이러한 풀이 방식을 활용한 문제가 나왔었다.

훨씬 더 어려운 구현 문제 였지만 스테디하게 활용되는 방식이다.

---

문제설명

링크참조

https://www.acmicpc.net/problem/4179

 

---

내풀이

1. 불을 먼저 진행시킨다.

불을 먼저 진행시키는 이유는 불의 진행은 지훈이에게 영향을 주지만 , 영향을 받지는 않는다.

우선 불을 진행시키고 dist배열에 시간을 기록한다.

 

2. 지훈이가 진행한다.

지훈이가 진행할때 이동하는 위치가 배열을 벗어나면 성공적으로 벗어난 것이므로 현재거리+1출력

지훈이가 진행 

-> 불 거리 배열의 숫자보다 크면 , 불이 번진곳이므로 가지 못한다 continue 

-> 진행 가능 : 현재 거리 + 1 & 큐에 추가

 

만약 지훈이의 큐가 엠티할때까지 출력이 안되면 IMPOSSIBLE을 출력하면 된다.

불쌍한 지훈이는 탈출하지 못한거니까. 

 

이게  처음 코드인데 계속 61퍼에서 틀렸다.

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

class Main {
	static class Node {
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		char[][] board = new char[R][C];
		fireDist = new int[R][C];
		jhDist = new int[R][C];
		ArrayDeque<Node> fq = new ArrayDeque<>();
		ArrayDeque<Node> jq = new ArrayDeque<>();
		for (int i = 0; i < R; i++) {
			String s = br.readLine();
			for (int j = 0; j < C; j++) {
				char v = s.charAt(j);
				board[i][j] = v;
				if (v == 'J')
					jq.offer(new Node(i, j));
				if (v == 'F')
					fq.offer(new Node(i, j));
			}
		}
		// 불먼저 진행 시간을 저장한다.
		while (!fq.isEmpty()) {
			Node cur = fq.poll();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				if (nx < 0 || nx >= R || ny <0 || ny >= C) continue;
				if (board[nx][ny] != '.' || fireDist[nx][ny] > 0) continue;
				fireDist[nx][ny] = fireDist[cur.x][cur.y] +1 ;
				fq.offer(new Node(nx,ny));
			}
		}

		// 지훈이가 시작할때 불의 시간보다 작아야지 통과
		// 범위 밖으로 나가면 그때 cost 출력 만약에 q가 엠티 될때까지 못나가면 IMPOSSIBLE출력
		while (!jq.isEmpty()) {
			Node cur = jq.poll();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				if (nx < 0 || nx >= R || ny <0 || ny >= C) {
					System.out.println(jhDist[cur.x][cur.y] +1 );
					return;
				}
				if (board[nx][ny] != '.' || jhDist[nx][ny] > 0) continue;
				if (fireDist[nx][ny] <= jhDist[cur.x][cur.y] +1) continue;
				jhDist[nx][ny] = jhDist[cur.x][cur.y] +1 ;
				jq.offer(new Node(nx,ny));
			}
		}
		System.out.println("IMPOSSIBLE");

	}
}

 

이 코드에서 틀린 부분은 바로 이 부분 이였다.

 

while (!jq.isEmpty()) {
			Node cur = jq.poll();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				if (nx < 0 || nx >= R || ny <0 || ny >= C) {
					System.out.println(jhDist[cur.x][cur.y] +1 );
					return;
				}
				if (board[nx][ny] != '.' || jhDist[nx][ny] > 0) continue;
				if (fireDist[nx][ny] <= jhDist[cur.x][cur.y] +1) continue;
				jhDist[nx][ny] = jhDist[cur.x][cur.y] +1 ;
				jq.offer(new Node(nx,ny));
			}
		}

 

바로 불이 번진 곳이 지훈이가 이동할 시간보다 작거나 같으면 continue하는 문인데

여기서 계속 틀린 이유는 불이 번지지 않았을 경우 0 인데, 그러면 지훈이는 문제없이 지나갈수 있어야된다

그 부분을 고려하지 않았고, 조건식을 fireDist[nx][ny] > 0 을 추가해서 해결했다. 

아래는 최종 코드다.

 

---

정답 코드 

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

class Main {
	static class Node {
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		char[][] board = new char[R][C];
		fireDist = new int[R][C];
		jhDist = new int[R][C];
		ArrayDeque<Node> fq = new ArrayDeque<>();
		ArrayDeque<Node> jq = new ArrayDeque<>();
		for (int i = 0; i < R; i++) {
			String s = br.readLine();
			for (int j = 0; j < C; j++) {
				char v = s.charAt(j);
				board[i][j] = v;
				if (v == 'J')
					jq.offer(new Node(i, j));
				if (v == 'F')
					fq.offer(new Node(i, j));
			}
		}
		// 불먼저 진행 시간을 저장한다.
		while (!fq.isEmpty()) {
			Node cur = fq.poll();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				if (nx < 0 || nx >= R || ny <0 || ny >= C) continue;
				if (board[nx][ny] != '.' || fireDist[nx][ny] > 0) continue;
				fireDist[nx][ny] = fireDist[cur.x][cur.y] +1 ;
				fq.offer(new Node(nx,ny));
			}
		}

		// 지훈이가 시작할때 불의 시간보다 작아야지 통과
		// 범위 밖으로 나가면 그때 cost 출력 만약에 q가 엠티 될때까지 못나가면 IMPOSSIBLE출력
		while (!jq.isEmpty()) {
			Node cur = jq.poll();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];
				if (nx < 0 || nx >= R || ny <0 || ny >= C) {
					System.out.println(jhDist[cur.x][cur.y] +1 );
					return;
				}
				if (board[nx][ny] != '.' || jhDist[nx][ny] > 0) continue;
				if (fireDist[nx][ny] > 0 &&fireDist[nx][ny] <= jhDist[cur.x][cur.y] +1) continue;
				jhDist[nx][ny] = jhDist[cur.x][cur.y] +1 ;
				jq.offer(new Node(nx,ny));
			}
		}
		System.out.println("IMPOSSIBLE");

	}
}

 

우선 불의 진행으로 인해서 지훈이의 진행은 영향받지만, 불은 지훈이의 진행의 영향을 받지않아서 불의 진행을 먼저 하는게 가능했다.

하지만 둘의 진행이 서로 연관되어 있을 경우는 생각해야 될 것이 많다.

서로 연관되어 있는 문제의 링크다.

https://www.acmicpc.net/problem/18809