글 읽기 - 4179 불! 어디가 틀렸는지 모르겠네요;;

donggyun 3년 전 0

안녕하세요.

BFS 공부중에 너무 답답해서 처음으로 질문을 올리게 되네요. ㅜㅜ

질문에 올라온 케이스도 넣어보고 했을때 정상적인 답변이 나오는데

제출하면 틀렸다고 나옵니다.

어느 부분이 틀린지 알려주시면 정말 감사하겠습니다!

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

public class Main {
	static int R, C;
	static int[][] board = new int[1001][1001];
	static int[][] visit = new int[1001][1001];
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		Queue<Pair> Q = new LinkedList<Pair>();
		Queue<Pair> FQ = new LinkedList<Pair>();
		
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				switch (str.charAt(j)) {
				case '#':
					board[i][j] = 9;
					break;
				case 'J':
					board[i][j] = 1;
					visit[i][j] = 1;
					Q.offer(new Pair(i,j));
					break;
				case 'F':
					board[i][j] = 4;
					FQ.offer(new Pair(i,j));
					break;
				default:
					break;
				}
			}			
		} // for
		
		boolean b = false;
		int maxValue = 0;
		
		while (!Q.isEmpty()) {
			int qSize = Q.size();
			for (int isize = 0; isize < qSize; isize++) {
			Pair cur = Q.poll();
			
				for (int i = 0; i < dx.length; i++) {
					int nx = cur.x + dx[i];
					int ny = cur.y + dy[i];
					
					if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
						b = true;
						maxValue = visit[cur.x][cur.y];
						break;
					}
					if (board[nx][ny] == 4 || board[nx][ny] == 9 || board[nx][ny] == 1) continue;
					
					board[nx][ny] = 1;
					visit[nx][ny] = visit[cur.x][cur.y] + 1;
					
					Q.offer(new Pair(nx,ny));
				}
				
				if (b) break;
			}
			
			if (b) break;
			
			int fqSize = FQ.size();
			for (int fsize = 0; fsize < fqSize; fsize++) {
				Pair fireCur = FQ.poll();
				
				for (int i = 0; i < dx.length; i++) {
					int nx = fireCur.x + dx[i];
					int ny = fireCur.y + dy[i];
					
					if (nx < 0 || nx >= R || ny < 0 || ny >= C)  continue;
					if (board[nx][ny] == 9 || board[nx][ny] == 4) continue;
					
					board[nx][ny] = 4;
					FQ.offer(new Pair(nx,ny));
				}
			}
			
		}
		
		// 확인 출력
//		for (int i = 0; i < R; i++) {
//			for (int j = 0; j < C; j++) {
//				System.out.print(board[i][j]);				
//			}
//			System.out.println();
//		}
//		System.out.println();
//		
//		for (int i = 0; i < R; i++) {
//			for (int j = 0; j < C; j++) {
//				System.out.print(visit[i][j]);				
//			}
//			System.out.println();
//		}
//		System.out.println();
		
		
		if (b) System.out.println(maxValue);
		else System.out.println("IMPOSSIBLE");
		
	}
}


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

donggyun 3년 전 0

자답입니다.

범위에 벗어난것이 무조건 탈출인줄 알았는데,

제 로직에는 jason 경로 이후에 fire 의 경로를 엎어씌우다보니

이미 큐에 들어간 있는 jason 의 이동경로가 범위 밖으로 넘어가면서 오답이 나오고 있었습니다.

범위를 벗어나는 조건을 추가하여 수정하였습니다.

수정한 코드 아래에 올립니다.

if (nx < 0 || nx >= R || ny < 0 || ny >= C) {

if (board[cur.x][cur.y] != 4) {

b = true;

maxValue = visit[cur.x][cur.y];

break;

} else {

continue;

}

view7186 1년 전 0

감사합니다! 저도 비슷한 방법으로 틀려서 원인을 찾고 있었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4179 불! 어디가 틀렸는지 모르겠네요;;

donggyun 3년 전 0

donggyun 3년 전 0

view7186 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말