글 읽기 - 2178 미로문제 왜 틀렸다고 나올까요..?

mylee1124 6년 전 0

이클립스에서는 답이 제대로 나오구요

다른 테스트케이스를 만들어서 입력해봐도 답이 제대로 나옵니다.

그런데 채점할 경우 틀렸습니다로 나오네요 ㅠㅠ

어디가 문제일까요?

답변 부탁드립니다.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point {
	int x, y, cnt;
	public Point(int x, int y, int cnt) {
		this.x = x;
		this.y = y;
		this.cnt = cnt;
	}
}

public class Main {

	public static void bfs(int n, int m, int[][] map) 
	{
		Queue<Point> queue = new LinkedList<>();
		Point stPt = new Point(0, 0, 1);
		queue.add(stPt);
		int shortest = 0;
		while(!queue.isEmpty())
		{
			Point cur = queue.remove();
			int[] xArray = {-1, 0,1,0};
			int[] yArray ={0,-1,0,1};
			
			for(int i=0; i<xArray.length; i++)
			{
				int endPtX = cur.x + xArray[i];
				int endPtY = cur.y + yArray[i];
				
				if(endPtX>=0 && endPtX<n && endPtY>=0 && endPtY<m
						&& map[endPtX][endPtY]==1)
				{
					map[endPtX][endPtY]=0; //방문표시
					//shortest = cur.cnt;
					queue.add(new Point(endPtX, endPtY, cur.cnt+1));
					shortest = cur.cnt;
				}
			}
		}
		
		System.out.println(shortest+1);
		
		
	}

	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int map[][] = new int[n][m];
		
		for(int i=0; i<n; i++)
		{
			String s = sc.next();
			char[] temp=s.toCharArray();
			
			for(int j=0; j<m; j++)
			{
				map[i][j]=temp[j]-'0';
			}
			
		}
		
		bfs(n, m, map);

	}
}

imgosari 6년 전 0

n개의 줄, m개의 칸이 입력되는데

if(endPtX>=0 && endPtX<n && endPtY>=0 && endPtY<m && map[endPtX][endPtY]==1) 이 부분에서는 x를 n과, y를 m과 비교하네요.

그리고 방문했다는 표시가 0인가요?

자바에서 배열을 생성하면 초기값이 1로 된다면 이 경우가 맞을 것 같은데...(자바한지 오래되서 0으로 초기화되는지 1로 초기화가 가능한지는 기억이 나지 않습니다.)

만약 자바에서 배열이 0으로 초기화된다면 endPtX와 endPtY를 map[endPtX][endPtY]==0인 경우 탐색을 시작하고 map[endPtX][endPtY]==1로 할당하는 것이 옳다고 봅니다.

imgosari 6년 전 0

위 부분 고려하셔서 테스트 해보시고 답변 해주세욤

mylee1124 6년 전 0

문제에서 미로를 입력받고 1일 경우 지나갈 수 있고 0일 경우에는 지나갈 수 없도록 되어있어서

map[endPtX][endPtY]==1 인 경우 큐에다가 넣어주었습니다.

그리고 방문한 경우 map[endPtX][endPtY]=0으로 해주어 지나가지 다음번에 탐색할 경우 지나가지 못하도록 해주었습니다.

if(endPtX>=0 && endPtX<n && endPtY>=0 && endPtY<m && map[endPtX][endPtY]==1)

이 부분은 4행 6열의 배열을 입력받은 경우

배열의 행은 0~3 사이에 있을 경우, 열은 0~5 사이에 있을 경우 유효하다는 것을 검사하기 위해 입력한 것입니다.

수정해야 할 부분이 어떤 부분인지 정확히 말씀해주시면 감사하겠습니다 ㅠㅠ

P.S Boolean 배열을 만들어서 방문한 경우를 체크하도록 해주었는데도 안되네요 ㅠㅠ 다른 방법이 있을까요 ?

imgosari 6년 전 0

음; 입력을 N과 M을 받으면.. 문자판의 행과 열이 들어오니까,

x는 M과 관계있고 y는 N과 관계있는 것이 아닌가요?

map 배열 생성하실 때도 map[N][M]으로 잡으셨는데..

if(endPtX>=0 && endPtX<n && endPtY>=0 && endPtY<m)이 아니라

if(endPtX>=0 && endPtX<m && endPtY>=0 && endPtY<n)으로 해야 하는거 아닐까요

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

문제

문제

출처

ICPC

2178 미로문제 왜 틀렸다고 나올까요..?

mylee1124 6년 전 0

imgosari 6년 전 0

imgosari 6년 전 0

mylee1124 6년 전 0

imgosari 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말