글 읽기 - 미로찾기 문제인데요... 자꾸 메모리 초과 에러가 뜨네요 ㅠㅠ

loginluv 4년 전 0

visited 표시를 위해 이미 방문한 노드는 '0'으로 표기했는데,

실행시킬떄 마다 메모리 초과 에러가 떠요 ㅠㅠ

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

public class Main
{
  static int N;
  static int M;
  static char [][] map = new char[100][100];
  public static void main (String[]args)
  {

    Scanner sc = new Scanner (System.in);
    String input = sc.nextLine ();

      N = Integer.parseInt (input.split (" ")[0]);
      M = Integer.parseInt (input.split (" ")[1]);

    for (int i = 0; i < N; i++)
      {
	input = sc.nextLine ();
	char[] arr = input.toCharArray ();

	for (int j = 0; j < M; j++)
	  {
	    map[i][j] = arr[j];
	  }
      }

    System.out.println (bfs ());

  }

  public static int bfs ()
  {

    LinkedList < Coord > queue = new LinkedList < Coord > ();
    int curRow;
    int curCol;
    int curDist;
    int ret = 1;
    queue.add (new Coord (0, 0, 1));

    while (!queue.isEmpty ())
      {
	Coord co = (Coord) queue.poll ();
	curRow = co.row;
	curCol = co.col;
	curDist = co.dist;
	map[curRow][curCol] = '0';
	//System.out.println (curRow + ", " + curCol + " : " + curDist);
	if (curRow == N - 1 && curCol == M - 1)
	  {
	    ret = curDist;
	    break;
	  }
	// up
	if (curRow - 1 >= 0 && map[curRow - 1][curCol] == '1')
	  queue.add (new Coord (curRow - 1, curCol, curDist + 1));
	// down
	if (curRow + 1 < N && map[curRow + 1][curCol] == '1')
	  queue.add (new Coord (curRow + 1, curCol, curDist + 1));
	// left
	if (curCol - 1 >= 0 && map[curRow][curCol - 1] == '1')
	  queue.add (new Coord (curRow, curCol - 1, curDist + 1));
	// right
	if (curCol + 1 < M && map[curRow][curCol + 1] == '1')
	  queue.add (new Coord (curRow, curCol + 1, curDist + 1));

      }
      queue.clear();
    return ret;
  }


}

  class Coord
  {
    int row, col;
      int dist;

    public Coord (int row, int col, int dist)
    {
      this.row = row;
      this.col = col;
      this.dist = dist;
    }
  }

nahwasa 4년 전 4

방문체크를 49번재줄에서 하시면 안되고, 넣으면서 하셔야 합니다.

예를들어보죠.

1 2 3
4 5 6
7 8 9

모두 데이터상으론 1인데 설명 편의를 위해 숫자를 붙였습니다.

1을 큐에 넣고 0으로 바꿈.
2랑 4를 큐에 넣음.
2를 poll하고 2를 0으로 바꾸고 3과 5를 넣음.
4를 poll하고 4를 0으로 바꾸고 5와 7을 넣음.
3을 poll하고 0으로 바꾸고 6을 넣음.

0 0 0
0 5 6
7 8 9

현재 상태입니다.

6. 5를 poll하고 0으로 바꾸고 6과 8을 넣음

7. 5를 poll하고 0이지만 또 0으로 바꾸고 6과 8을 넣음

8. ...

보시다시피 중복으로 들어가는게 생기게 되면 계속 불어나게됩니다.

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

문제

문제

출처

ICPC

미로찾기 문제인데요... 자꾸 메모리 초과 에러가 뜨네요 ㅠㅠ

loginluv 4년 전 0

nahwasa 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말