글 읽기 - 12%에서 틀렸다고 나오는데 이유를 모르겠네요ㅠㅠ

yoseong92 4년 전 0

뭐가 문제인지 알려주세요ㅠㅠㅠㅠㅠㅠㅠㅠ

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

public class Main {
	static int n;
	static int m;
	static int[][] map = new int[100][100];
	static int[][] visited = new int[100][100];
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		m = scanner.nextInt();
		
		String temp;
		
		for (int i = 0; i < n; i++) {
			temp = scanner.next();
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(temp.charAt(j)+"");
			}
		}
		bfs();
	}
	
	private static void bfs() {
		
		int a, b, result = 1;
		int flag = 0;
		int len[] = {-1, 0, 0, 1};
		int wid[] = {0, 1, -1, 0};
		
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);
		
		while (flag != 1) {
			
			for (int i = 0; i < queue.size(); i++) {
				int temp = queue.poll();
				a = temp / 100;
				b = temp % 100;
				
				if (a == n - 1 && b == m - 1) {
					System.out.println(result);
					flag = 1;
				}
				
				for (int j = 0; j < 4; j++) {
					int nextA = a + wid[j];
					int nextB = b + len[j];
					if (nextA >= n || nextA < 0 || nextB >= m || nextB < 0)
						continue;
					if (map[nextA][nextB] == 0) 
						continue;
					if (visited[nextA][nextB] == 1)
						continue;
					
					visited[nextA][nextB] = 1;
					queue.add(nextA*100 + nextB);
				}				
			}
			result++;
		}
	}
}

djm03178 4년 전 1

for문을 queue.size() 까지 돌리면, for문을 도는 도중에도 큐에 새로운 원소가 추가되면서 크기가 늘어나기 때문에 정확하게 개수를 세지 못합니다.

3 3

111

5번만에 갈 수 있지만, 4가 출력됩니다.

yoseong92 4년 전 0

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

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

문제

문제

출처

ICPC

12%에서 틀렸다고 나오는데 이유를 모르겠네요ㅠㅠ

yoseong92 4년 전 0

djm03178 4년 전 1

yoseong92 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말