글 읽기 - [JAVA] 토마토문제 bfs 구현// 답답해서 질문 드립니다.

kisrin4319 7년 전 0

일반적인 bfs 알고리즘으로 문제를 해결하려 했습니다.

문제에 나와 있는 테스트 케이스는 올바르게 나오나 밑의 케이스 (11,11)의 경우 답은 4인데 제 코드로 돌리면 48이 자꾸 나와 수정하려고 했는데 도저히 모르겠습니다.

다른 분들의 질문 글을 보았는데 다른점이 있다면 29~35 Line 인것 같습니다. 다른 분들은 바로 큐에 집어넣었지만 저는 해당 조건마다 bfs 함수를 불러 해결하고자 했는데 잘못 된걸까요?

위의 방식과 다르게 현재 제 코드로는 어떻게 수정해야 될지 알려주셨으면 감사하겠습니다.

11 11
0 0 0 0 1 0 -1 -1 0 0 0 
0 -1 1 1 0 0 1 1 0 0 0 
0 0 0 0 -1 1 0 0 1 0 0 
0 0 -1 0 0 -1 -1 0 0 0 -1 
1 1 -1 0 0 1 0 0 0 -1 1 
-1 0 0 0 0 0 1 0 0 1 0 
0 1 0 -1 0 0 0 0 1 1 1 
0 0 0 1 0 0 0 0 0 -1 0 
0 0 0 0 0 0 0 0 0 0 -1 
-1 0 0 0 0 0 1 1 0 0 1 
-1 0 0 0 0 -1 -1 0 0 0 -1

import java.io.*;
import java.math.*;
import java.util.*;
public class Main {

	public static PrintWriter out;
	static int[][] ad;
	static boolean[][] visit;
	static int M;
	static int N;
	static int day=-1;
	static int[] dx ={0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	public static void main(String[] args) throws IOException
	{
		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));
		M = sc.nextInt();
		N = sc.nextInt();
		ad= new int[N][M];
		visit = new boolean[N][M];
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<M;j++)
			{
				ad[i][j] = sc.nextInt();
			}
		}
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++){
				if(visit[i][j]==false && ad[i][j]==1){
					bfs(i,j);
				}
			}
		}
		boolean check = true;
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<M;j++)
			{
				if(ad[i][j]==0){
					check = false;
					break;
				}
			}
		}
		if(check == false){
			out.println(-1);
		}
		else{
			out.println(day);
		}
		out.close();
	}
	private static void bfs(int row, int col) {
	
		Queue<Point> q = new LinkedList<Point>();
		Point p = new Point(row,col);
		q.add(p);
		while(!q.isEmpty())
		{
			int size = q.size();
			for(int sz =0; sz<size;sz++)
			{
				p = q.poll();
				int x = p.x;
				int y = p.y;
				for(int ar=0;ar<4;ar++)
				{
					int cx = x+dx[ar];
					int cy = y+dy[ar];
					if(cx>=0 && cx<N && cy>=0 && cy<M)
						if(ad[cx][cy]==0 && visit[cx][cy]==false)
						{
							ad[cx][cy]=1;
							visit[cx][cy]=true;
							q.add(new Point(cx,cy));
						}
				}
			}
			day++;
		}
	}
}
class Point{
	int x;
	int y;
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

wowoto9772 7년 전 0

각 해당하는 칸에 토마토가 도달하는 최소 시간을 저장해주는 구조가 되야하지 않을까요???

010

000

111

010

111

212

kisrin4319 7년 전 0

흠.. 댓글을 읽고서 75라인을 ad[cx][cy] =1 대신에 ad[cx][cy]= ad[x][y]+1; 이런식으로 해서 행렬 전체를 확인해봤는데도 이상하게 나오네요 ㅠㅠ

wowoto9772 7년 전 0

전체 솔루션 코드좀 올려주세요 !!!!

kisrin4319 7년 전 0

이게 전체 소스 코드입니다!

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


//-----------MyScanner class for faster input----------
class MyScanner {
	BufferedReader br;
	StringTokenizer st;

	public MyScanner() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	String next() {
		while (st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt() {
		return Integer.parseInt(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}
}

public class Main {

	public static PrintWriter out;
	static int[][] ad;
	static boolean[][] visit;
	static int M;
	static int N;
	static int[] dx ={0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	public static void main(String[] args) throws IOException
	{
		MyScanner sc = new MyScanner();
		out = new PrintWriter(new BufferedOutputStream(System.out));
		M = sc.nextInt();
		N = sc.nextInt();
		ad= new int[N][M];
		visit = new boolean[N][M];
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<M;j++)
			{
				ad[i][j] = sc.nextInt();
			}
		}
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++){
				if(visit[i][j]==false && ad[i][j]==1){
					bfs(i,j);
				}
			}
		}
		for(int i=0;i<N;i++){ //ad 배열 값 확인용
			for(int j=0;j<M;j++){
				out.printf(ad[i][j]+" ");			
			}
			out.println();
		}
		boolean check = true;
		int ans = 1;
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<M;j++)
			{
				if(ad[i][j]==0){
					check = false;
					break;
				}
				ans = Math.max(ans, ad[i][j]);
			}
		}
		if(check == false){
			out.println(-1);
		}
		else{
			out.println(ans-1);
		}
		out.close();
	}
	private static void bfs(int row, int col) {
	
		Queue<Point> q = new LinkedList<Point>();
		Point p = new Point(row,col);
		q.add(p);
		while(!q.isEmpty())
		{
			int size = q.size();
			for(int sz =0; sz<size;sz++)
			{
				p = q.poll();
				int x = p.x;
				int y = p.y;
				for(int ar=0;ar<4;ar++)
				{
					int cx = x+dx[ar];
					int cy = y+dy[ar];
					if(cx>=0 && cx<N && cy>=0 && cy<M)
						if(ad[cx][cy]==0 && visit[cx][cy]==false)
						{
							ad[cx][cy]=ad[x][y]+1;
							visit[cx][cy]=true;
							q.add(new Point(cx,cy));
						}
				}
			}
		}
	}
}
class Point{
	int x;
	int y;
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

wowoto9772 7년 전 0

다른 소스코드 부분은 모두 맞다고 가정하면,

66번째 라인이 문제가 되는 라인 같네요.

초기에 토마토가 놓여있는 위치가 시작점이 되어야 합니다

(초기에 토마토가 여러개라면 , 여러개의 위치가 동시에 시작점이 되도록 해야합니다.)

지금 솔루션을 보면,

0101

0000

1111

0100

1111

2120

1111

2123

이렇게 되는 것 같아요.

kisrin4319 7년 전 0

흠 그렇다면 for문을 돌려서 1이 등장하는 i,j 때마다 함수를 불러서 하는건 안되나보네요..

다른분들 처럼 바로 큐에 넣어서 해야되나봅니다 ㅠㅠ..

kdk8361 7년 전 0

최소값 제대로 나오나요? 나중에 들어간 1에서 더 빨리 도착하는 경우도 있을텐데요.

kisrin4319 7년 전 0

kdk8361 // 문제 아래에 있는 테스트 케이스는 제대로 나오지만 나머지 케이스는 잘 나오지 않는것 같습니다.

정올에서 돌려봤는데 accepted(30)이 나오는걸 보면 특정 케이스에서만 맞는거 같아요

kdk8361 7년 전 0

visited 대신 ad[cx][cy]와 ad[x][y]의 값을 비교해서 더 작은값이 들어가도록 하는 방법도 있습니다.

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

문제

문제

출처

ICPC

[JAVA] 토마토문제 bfs 구현// 답답해서 질문 드립니다.

kisrin4319 7년 전 0

wowoto9772 7년 전 0

kisrin4319 7년 전 0

wowoto9772 7년 전 0

kisrin4319 7년 전 0

wowoto9772 7년 전 0

kisrin4319 7년 전 0

kdk8361 7년 전 0

kisrin4319 7년 전 0

kdk8361 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말