글 읽기 - 예제는 알맞게 나오는데 틀렸다고 나와요 ㅠㅠ 도와주세요

rorean 6년 전 0

도와주세요 고수님들 ㅠㅠ bfs로 풀었고 구글링한거 참고해서 풀었는데.. 순서만 다르고 로직은 같은데 제것만 틀렸대요 ㅠㅠ
14% 지나서 바로 틀렸다고 나옵니다.. 어디가 문제인지 못찾겠어여 ㅜㅜ

import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	static int n;
	static int m;
	static int[][] maze;
	static int[][] visited;
	static ArrayList<Point> qu;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		n = scan.nextInt();
		m = scan.nextInt();
		
		maze = new int[n][m];
		visited = new int[n][m];
		
		scan.nextLine();
		for(int i = 0 ; i < n ; i++) {
			String num = scan.nextLine();
			for (int j = 0; j < m ; j++) {
				maze[i][j] = Integer.parseInt(num.substring(j, j+1));
			}
		}
		
		qu = new ArrayList<Point>();

		BFS(0, 0);
	}
	
	//0,1 1,0 0,-1 -1,0
	public static void BFS(int x, int y) {
		int[] _x = { 1, -1, 0, 0 };
		int[] _y = { 0, 0, 1, -1 };
		int count = 0;
		qu.add(new Point(x,y));
		visited[x][y] = 1;
		
		while (!qu.isEmpty()) {
			
			count ++ ;
			int size = qu.size();
			for ( int j = 0 ; j < size; j ++) {
				int curr_x = qu.get(0).x;
				int curr_y = qu.get(0).y;
				qu.remove(0);
				
				if (curr_x == n -1 && curr_y == m-1) {
					break;
				}
				
				for ( int i = 0; i < 4 ; i++) {
					int next_x = _x[i] + curr_x;
					int next_y = _y[i] + curr_y;
					
					if (next_x >= 0 && next_y >= 0 && next_x < n && next_y < m) {
						if ( maze[next_x][next_y] == 1 && visited[next_x][next_y] == 0) {
							visited[next_x][next_y] = 1;
							qu.add(new Point(next_x, next_y));

						}
					}
				}
				
			}

		}
		System.out.println(count);
	}
}

djm03178 6년 전 1

if (curr_x == n -1 && curr_y == m-1) {

break;
}

이걸 한다고 해서 탐색이 종료되지 않습니다. 그냥 break;는 가장 안쪽의 루프 하나만 빠져나가기 때문이죠. 따라서 이 문장이 실행된 후에도 큐가 비어있지 않다면 탐색을 계속해서 진행하게 됩니다.

4 4
1011
1010
1111

0001

7번만에 탐색이 종료되어야 하지만, 8을 출력합니다.

rorean 6년 전 0

감사합니다!! 덕분에 해결했습니다 !!!!!!!

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

문제

문제

출처

ICPC

예제는 알맞게 나오는데 틀렸다고 나와요 ㅠㅠ 도와주세요

rorean 6년 전 0

djm03178 6년 전 1

rorean 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말