글 읽기 - 한달 뒤 다시 풀어봤는데 여전히 못풀겠습니다 ㅠㅠ

le_effort 1년 전 0

도저히 게시판 보고 해보려고 해도 못풀겠어서

한달 뒤 실력 좀 키우고 풀어보자 라는 생각으로

오늘 다시 풀어봤는데요 여전히 틀렸습니다가 뜹니다 ㅠㅠ..

정말 이 문제 뭐가 잘못 된 건지 꼭 알고 싶은데 모르니 답답해 미칠 지경입니다

도와주시면 정말 감사하겠습니다..

생각한 기본 알고리즘은 불 bfs , 사람 bfs 따로 만들어서

불 bfs를 먼저 돌리고 장애물이 없을때 걸리는 시간을 체크 해줍니다 (fire_time)

그 다음 일반 bfs로 장애물이 없고 fire_time 과 일반 time을 비교해서 fire_time 이 더 크면 탈출 가능하니 큐에 넣어주는 식으로 했습니다 ㅠ

import java. io.*;
import java. util.*;
public class Main {
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int[][] time;
	static String[][] arr;
	static int h,w;
	static Queue<Node> q = new LinkedList<>();
	static boolean visited[][];
	static boolean fire_visited[][];
	static int fire_time[][];
	static Queue<Node>fire_q = new LinkedList<>();
	static boolean bl;
	static int fin_x, fin_y;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test_case = Integer.parseInt(br.readLine());
		
		for(int m=0; m<test_case; m++) {
			fin_x = Integer.MAX_VALUE;
			fin_y = Integer.MAX_VALUE;
			bl = false;
			q.clear();
			fire_q.clear();
			String[] t = br.readLine().split(" ");
			w = Integer.parseInt(t[0]);		// 너비
			h = Integer.parseInt(t[1]);		//높이
			arr = new String[h][w];
			time = new int[h][w];
			fire_time = new int[h][w];
			fire_visited = new boolean[h][w];
			visited = new boolean[h][w];

			for(int i=0; i<h; i++) {
				String[] input = br.readLine().split("");
				for(int j=0; j<w; j++) {
					arr[i][j] = input[j];
					if(arr[i][j].equals("@")) {
						q.add(new Node(i,j));  	// 시작위치를 넣어준다
						if(i==0 || j==0 || i==h-1 || j==w-1) {
							fin_x=0;
							fin_y=0;
							bl = true;					
						}
					}
					if(arr[i][j].equals("*")) {
						fire_q.add(new Node(i,j));
					}
				}
			}
			fire_bfs();
			bfs();

			if(bl) {
				System.out.println(time[fin_x][fin_y]+1);
			}
			else {
				System.out.println("IMPOSSIBLE");
			}
		}
		
	}
	public static void fire_bfs() {
		while(!fire_q.isEmpty()) {
			Node a = fire_q.poll();
			fire_visited[a.x][a.y] = true;
			for(int i=0; i<4; i++) {
				int x_1 = a.x+dx[i];
				int y_1 = a.y +dy[i];
				if(x_1>=0 && y_1>=0 && x_1<h && y_1<w) {
					if(!fire_visited[x_1][y_1] && !arr[x_1][y_1].equals("#")) {
						fire_visited[x_1][y_1] = true;
						fire_time[x_1][y_1] = fire_time[a.x][a.y]+1;
						fire_q.add(new Node(x_1,y_1));
					}
				}
			}
		}
	}
	public static void bfs() {
		while(!q.isEmpty()) {
			Node a = q.poll();
			visited[a.x][a.y] = true;
			for(int i=0; i<4; i++) {
				int x_1 = a.x+dx[i];
				int y_1 = a.y+dy[i];
				if(x_1>=0 && y_1>=0 && x_1<h && y_1<w) {
					
					if(!visited[x_1][y_1] && arr[x_1][y_1].equals(".")) {
						if(!visited[x_1][y_1] && fire_time[x_1][y_1]>time[a.x][a.y]) {
							visited[x_1][y_1] = true;
							q.add(new Node(x_1,y_1));
							time[x_1][y_1] = time[a.x][a.y]+1;
							if(x_1==0 || y_1==0 || x_1==h-1 || y_1==w-1) {
								bl = true;
	
								fin_x = Math.min(fin_x,x_1);
								fin_y = Math.min(fin_y, y_1);
							}
						}
					}
				}
			}
		}
	}
}
class Node{
	int x;
	int y;
	
	Node(int x, int y){
		this.x= x;
		this. y= y;
	}
}

djm03178 1년 전 1

불이 지나갈 수 없는 곳의 fire_time이 0으로 설정되어 상근이도 못 지나가는 것으로 판정하고 있습니다.
나가는 x좌표와 y좌표가 최소가 되어야 할 이유가 하나도 없습니다. 중요한 것은 time[fin_x][fin_y]가 최소가 되는 것이지, fin_x, fin_y 자체가 최소가 되는 것이 아닙니다.

1
3 3
..#
#@#
###

le_effort 1년 전 0

충고해주신대로

불이 없는 경우 fire_time[x_1][y_1]==0 추가 해주었고
ans 라는 변수로 time의 최소값을 받고 정답 제출을 해보았는데

여지껏 바로 틀렸습니다가 뜨던게 33%까진 가고 틀렸다 라고 뜹니다

또 어떤걸 추가해야 하나요...??

귀중한 시간 내주셔서 정말 감사합니다....

import java. io.*;
import java. util.*;
public class Main {
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int[][] time;
	static String[][] arr;
	static int h,w;
	static Queue<Node> q = new LinkedList<>();
	static boolean visited[][];
	static boolean fire_visited[][];
	static int fire_time[][];
	static Queue<Node>fire_q = new LinkedList<>();
	static boolean bl;
	static int fin_x, fin_y;
	static int ans;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test_case = Integer.parseInt(br.readLine());
		
		for(int m=0; m<test_case; m++) {
			ans=Integer.MAX_VALUE;
			fin_x = Integer.MAX_VALUE;
			fin_y = Integer.MAX_VALUE;
			bl = false;
			q.clear();
			fire_q.clear();
			String[] t = br.readLine().split(" ");
			w = Integer.parseInt(t[0]);		// 너비
			h = Integer.parseInt(t[1]);		//높이
			arr = new String[h][w];
			time = new int[h][w];
			fire_time = new int[h][w];
			fire_visited = new boolean[h][w];
	
			
			visited = new boolean[h][w];

			for(int i=0; i<h; i++) {
				String[] input = br.readLine().split("");
				for(int j=0; j<w; j++) {
					arr[i][j] = input[j];
					if(arr[i][j].equals("@")) {
						q.add(new Node(i,j));  	// 시작위치를 넣어준다
						if(i==0 || j==0 || i==h-1 || j==w-1) {
							fin_x=0;
							fin_y=0;
							bl = true;					
						}
					}
					if(arr[i][j].equals("*")) {
						fire_q.add(new Node(i,j));
					}
				}
			}
			fire_bfs();
			bfs();

			if(bl) {
				System.out.println(ans+1);
			}
			else {
				System.out.println("IMPOSSIBLE");
			}
		}
		
	}
	public static void fire_bfs() {
		while(!fire_q.isEmpty()) {
			Node a = fire_q.poll();
			fire_visited[a.x][a.y] = true;
			for(int i=0; i<4; i++) {
				int x_1 = a.x+dx[i];
				int y_1 = a.y +dy[i];
				if(x_1>=0 && y_1>=0 && x_1<h && y_1<w) {
					if(!fire_visited[x_1][y_1] && !arr[x_1][y_1].equals("#")) {
						fire_visited[x_1][y_1] = true;
						fire_time[x_1][y_1] = fire_time[a.x][a.y]+1;
						fire_q.add(new Node(x_1,y_1));
					}
				}
			}
		}
	}
	public static void bfs() {
		while(!q.isEmpty()) {
			Node a = q.poll();
			visited[a.x][a.y] = true;
			for(int i=0; i<4; i++) {
				int x_1 = a.x+dx[i];
				int y_1 = a.y+dy[i];
				if(x_1>=0 && y_1>=0 && x_1<h && y_1<w) {
					
					if(!visited[x_1][y_1] && arr[x_1][y_1].equals(".")) {
						if(!visited[x_1][y_1] && fire_time[x_1][y_1]>time[a.x][a.y]+1 || fire_time[x_1][y_1]==0) {
							visited[x_1][y_1] = true;
							q.add(new Node(x_1,y_1));
							time[x_1][y_1] = time[a.x][a.y]+1;
							if(x_1==0 || y_1==0 || x_1==h-1 || y_1==w-1) {
								bl = true;
								ans=Math.min(ans, time[x_1][y_1]);
							}
						}
					}
				}
			}
		}
	}
}
class Node{
	int x;
	int y;
	
	Node(int x, int y){
		this.x= x;
		this. y= y;
	}
}

le_effort 1년 전 0

95번째줄 수정하고

101번째 줄 추가했습니다.

djm03178 1년 전 1

한 군데 덜 고친 곳이 있습니다.

https://ideone.com/y7ZBDm

le_effort 1년 전 0

아 해결했습니다 ㅠㅠㅠㅠㅠㅠㅠ

진짜 오랜 체증이 내려가는 기분입니드,,,

정말 감사합니다 좋은 하루 보내세요 !!!!!!1

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

문제

문제

출처

ICPC

한달 뒤 다시 풀어봤는데 여전히 못풀겠습니다 ㅠㅠ

le_effort 1년 전 0

djm03178 1년 전 1

le_effort 1년 전 0

le_effort 1년 전 0

djm03178 1년 전 1

le_effort 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말