글 읽기 - 런타임 에러 질문입니다.

mamamau 6년 전 0

어느 부분에서 런타임 에러가 나는 지 모르겠습니다.

큐에서 메모리를 너무 잡아먹기 때문일까요??

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

public class Monkey {
	static int[][] map;
	static int K;
	static int N;
	static int M;
	static boolean[][] visited;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int[] hx = {1,2,2,1,-1,-2,-2,-1};
	static int[] hy = {2,1,-1,-2,-2,-1,1,2};
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine().trim());
		String s = br.readLine().trim();
		N = Character.getNumericValue(s.charAt(0));
		M = Character.getNumericValue(s.charAt(2));
		map = new int[N][M];
		visited = new boolean[N][M];
		for(int i=0;i<N;i++) {
			s = br.readLine().trim();
			int t = 0;
			for(int j=0;j<M;j++) {
				map[i][j] = Character.getNumericValue(s.charAt(t));
				t+=2;
			}
		}
		System.out.println(bfs());
	}

	public static int bfs() {
		int cnt = 0;
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(0,0,0));
		while(!q.isEmpty()) {
			int qs = q.size();
			while(qs--!=0) {
				Point p = q.poll();
				visited[p.x][p.y] = true;
				if(p.x==N-1 && p.y==M-1) return cnt;
				for(int i=0;i<4;i++) {
					int cx = p.x + dx[i], cy = p.y + dy[i];
					if(chk(cx,cy) && !visited[cx][cy] && map[cx][cy]!=1)
						q.add(new Point(cx,cy,p.c));
				}
				if(p.c < K) {
					for(int i=0;i<8;i++) {
						int cx = p.x + hx[i], cy = p.y + hy[i];
						if(chk(cx,cy) && !visited[cx][cy] && map[cx][cy] != 1)
							q.add(new Point(cx,cy,p.c+1));
					}
				}
			}
			cnt++;
		}
		return -1;
	}
	
	public static boolean chk(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}
	
	public static class Point {
		public int x;
		public int y;
		public int c;
		public Point(int x, int y, int c) {
			this.x = x; this.y = y; this.c= c;
		}
	}
}

djm03178 6년 전 0

BFS에서는 pop할 때 방문 체크를 하는 것이 아니라 push할 때 해야 중복 방문이 일어나지 않습니다.

1 1

이런 상태에서 시작했을 때를 가정하면, 처음에 오른쪽 위, 왼쪽 아래가 큐에 들어가는데, 각각에서 오른쪽 아래를 넣을 때에도 방문 체크가 안 되어 있기 때문에 오른쪽 아래는 2번 큐에 들어가게 됩니다.

mamamau 6년 전 0

설명 감사합니다! 전혀 눈치채지 못하고 있었네요 ㅠㅠ

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

문제

문제

출처

ICPC

런타임 에러 질문입니다.

mamamau 6년 전 0

djm03178 6년 전 0

mamamau 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말