글 읽기 - 틀렸습니다..

shp9408 5년 전 0

안녕하세요

우선 bfs를 통해 호수의 각 칸마다 물이 차오르는 시간을 채운다음에

다음으로 백조 ->백조 이동하면서 위에서 구한 시간을 통해 최소 시간을 구해봤는데요.

어디 부분이 틀렸는지 잘모르겠습니다.. 도와주시면 감사하겠습니다..

(백조->백조 가 문제인것같습니다. )

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BJ3197 {
	static char[][] map;
	static int[][] visited; // 물이 차오르는 속도 
	static boolean[][] visited2; // 백조 -> 백조 시간 
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	public static void main(String[] args) {
		Scanner stdIn= new Scanner(System.in);
		int r = stdIn.nextInt();
		int c = stdIn.nextInt();
		stdIn.nextLine();
		map = new char[r][c];
		visited = new int[r][c];
		visited2 = new boolean[r][c];
		for(int i=0;i<r;i++) {
			String s =stdIn.nextLine();
			for(int j=0;j<c;j++) {
				map[i][j] = s.charAt(j);
			}
		}
		solve(r,c);
	}
	static void solve(int r, int c) {
		
		// 물이 차는 시간 계산
		Queue<Water> q = new LinkedList<Water>();
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(map[i][j] != 'X') {
					q.add(new Water(i,j));
					visited[i][j] = 1;
				}
			}
		}
		while(!q.isEmpty()) {
			Water h = q.remove();
			int x = h.x;
			int y = h.y;
			for(int i=0;i<4;i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx>=0 && ny >=0 && nx < r && ny < c) {
					if(visited[nx][ny] == 0) {
						q.add(new Water(nx,ny));
						visited[nx][ny] = visited[x][y] + 1;
					}
				}
			}
		}
		
		// 백조 투더 백조 
		ArrayDeque<Water2> dq = new ArrayDeque<Water2>();
		for(int i=0;i<r;i++) {
			boolean flag = false;
			for(int j=0;j<c;j++) {
				if(map[i][j] == 'L') {
					// 첫 백조 dq에 삽입 
					dq.addFirst(new Water2(i,j,0));
					map[i][j] = '.';
					visited2[i][j] = true;
					flag = true;
					break;
				}
			}
			if(flag == true) break;
		}
		while(!dq.isEmpty()) {
			Water2 h = dq.removeFirst();
			int x = h.x;
			int y = h.y;
			int t = h.t;
			if(map[x][y] == 'L') { // 백조 발견 
				System.out.println(t);
				return;
			}
			for(int i=0;i<4;i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx>=0 && ny >=0 && nx < r && ny < c) {
					if(visited[nx][ny] <= visited[x][y]) {
						if(visited2[nx][ny] == false) {
							dq.addFirst(new Water2(nx,ny,t));
							visited2[nx][ny] = true;
						}
					}
					else {
						if(visited2[nx][ny] == false) {
							dq.addLast(new Water2(nx,ny,t+1));
							visited2[nx][ny] = true;
						}
					}
				}
			}
		}
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				System.out.printf("%d ", visited[i][j]);
			}
			System.out.println();;
		}
//		System.out.println();;
//		for(int i=0;i<r;i++) {
//			for(int j=0;j<c;j++) {
//				System.out.printf("%d ", visited2[i][j]);
//			}
//			System.out.println();;
//		}
		
	}
}
class Water{
	int x;
	int y;
	Water(int x,int y){
		this.x = x;
		this.y = y;
	}
}
class Water2{
	int x;
	int y;
	int t;
	Water2(int x,int y, int t){
		this.x = x;
		this.y = y;
		this.t=t ;
	}
}

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

문제

문제

출처

ICPC

틀렸습니다..

shp9408 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말