글 읽기 - 문제 접근방식에 대한 질문입니다 ㅠ

le_effort 4년 전 0

생각한 알고리즘은

bfs 두개를 사용해서

첫째, 각 칸마다 물이 퍼지는 시간을 계산

둘째 각 칸마다 움직일수 있는 시간 계산 이때 그 칸이 D 라면 물이 도달하는데 걸리는 시간과 비교해서 더 빨리 도착한다면 탈출 성공

이것인데 첫번째 단계에서 그냥 벽이 아닐경우 시간을 계산하고 큐에 넣는데 만약 그 칸이 D라면 큐에 넣어주지 않습니다

큐에 안넣는 이유는 이렇게 했더니

도착 가능

불가 가능

이런 지도가 있을때 저기에 있는 불가능도 도착큐에 들어간 순간 상하좌우 과정을 통해서 시간이 측정이 됐습니다

두번째 bfs에서 시간을 계산하는 조건은 도착지의 상하좌우 인덱스의 시간을 비교해서 고슴도치가 더 빠르다면 출력하는 식으로 했는데

어떻게 고쳐야 할까요? 예제의 TC는 잘 되는데 틀렸습니다 뜨는거 보면 뭔가 로직에서 이상이 있는거 같습니다

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

public class Main {
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,1,-1};
	static String arr[][];
	static String water_arr[][];
	static boolean visited[][];
	static boolean water_visited[][];
	static int far[][];
	static int water_far[][];
	static int r,c;
	static int start_x,end_x , start_y, end_y;
	static boolean bl;
	static int fin_x , fin_y ;
	static Queue<Integer>q = new LinkedList<>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String [] t = br.readLine().split(" ");
		r = Integer.parseInt(t[0]);
		c = Integer.parseInt(t[1]);
		arr = new String[r][c];
		water_arr = new String[r][c];
		visited = new boolean[r][c];
		water_visited = new boolean[r][c];
		far = new int[r][c];
		water_far = new int[r][c];
		
		for(int i=0; i<r; i++) {
			String[] input = br.readLine().split("");
			for(int j=0; j<c; j++) {
				arr[i][j] = input[j];
				water_arr[i][j] =input[j];
				if(input[j].equals("S")) {
					start_x  = i;
					start_y= j;
				}
				if(input[j].equals("*")) {
					q.add(i);
					q.add(j);
				}
			}
		}	// 입력 끝
		water_bfs();
		bfs(start_x,start_y);
		if(bl) {
			System.out.println(far[fin_x][fin_y]);
		}
		else {
			System.out.println("KAKTUS");
		}
		System.out.println("water_far");
		/*for(int a=0; a<r; a++) {
			for(int b=0; b<c; b++) {
				System.out.print(water_far[a][b]);
			}
			System.out.println();
		}
		System.out.println();
		System.out.println("far");
		for(int a=0; a<r; a++) {
			for(int b=0; b<c; b++) {
				System.out.print(far[a][b]);
			}
			System.out.println();
		}*/

	}
	public static void water_bfs() {
		while(!q.isEmpty()) {
			int poll_x = q.poll();
			int poll_y = q.poll();
			water_visited[poll_x][poll_y] = true;
			for(int i=0; i<4; i++) {
	
				int x_1 = poll_x + dx[i];
				int y_1 = poll_y + dy[i];
				if(x_1>=0 && y_1>=0 && x_1<r && y_1<c) {
					if(!water_visited[x_1][y_1] && !arr[x_1][y_1].equals("X")) {
						water_visited[x_1][y_1] = true;
						if(arr[x_1][y_1].equals("D")) {
							water_far[x_1][y_1] =  water_far[poll_x][poll_y]+1;
						}
						else {
						water_far[x_1][y_1] =water_far[poll_x][poll_y]+1;
						q.add(x_1);
						q.add(y_1);
						}
	
					}
				}
			}
		}
	}
	public static void bfs(int x, int y) {
		Queue<Integer>q = new LinkedList<>();
		visited[x][y] = true;
		q.add(x);
		q.add(y);
		while(!q.isEmpty()) {
			int poll_x = q.poll();
			int poll_y = q.poll();
	
			for(int i=0; i<4; i++) {
				int x_1 = poll_x + dx[i];
				int y_1 = poll_y + dy[i];
	
				if(x_1>=0 && y_1>=0 && x_1<r && y_1<c) {
					if(!visited[x_1][y_1] && (!arr[x_1][y_1].equals("X") &&!arr[x_1][y_1].equals("*"))){
						far[x_1][y_1] = far[poll_x][poll_y]+1;
						q.add(x_1);
						q.add(y_1);
						visited[x_1][y_1]= true;

					}
					if(arr[x_1][y_1].equals("D")){
					for(int k=0; k<4; k++) {
						int tmp_x = x_1+dx[k];
			
						int tmp_y = y_1+dy[k];
						if(tmp_x>=0 && tmp_y >=0 && tmp_x<r && tmp_y<c) {
					
							if(water_far[tmp_x][tmp_y]!=0 && water_far[tmp_x][tmp_y] > far[tmp_x][tmp_y]) {
								bl = true;
								fin_x = x_1;
								fin_y = y_1;
								return ;
							}
						}
					}
				}
					/*if(arr[x_1][y_1].equals("D")) {
						System.out.println(x_1 + " " + y_1);
						System.out.println(far[x_1][y_1]);
						System.out.println(water_far[x_1][y_1]);
						//far[x_1][y_1]<water_far[x_1][y_1]
						System.out.println("?");
						bl = true;
						fin_x = x_1;
						fin_y = y_1;

						return ;
					}*/
				}
			}
		}
	}
	
}

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

문제

문제

출처

ICPC

문제 접근방식에 대한 질문입니다 ㅠ

le_effort 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말