글 읽기 - 메모리초과

syoungee 4년 전 0

메모리 초과 문제 질문입니다ㅠㅠ

visited가 문제인걸까요?ㅠㅠ

6%에서 메모리 초과가 뜨네요

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

class Pos {
	int x;
	int y;
	int time;

	public Pos(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public Pos(int x, int y, int time) {
		this.x = x;
		this.y = y;
		this.time = time;
	}
}

public class Main {

	public static int R;
	public static int C;
	public static char graph[][];
	public static boolean visited[][];
	public static int dx[] = { 1, -1, 0, 0 };
	public static int dy[] = { 0, 0, 1, -1 };
	public static Pos finish_point = null, curr_point = null;
	static LinkedList<Pos> water_list = new LinkedList<Pos>();
	public static boolean flag = false;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String temp = br.readLine();
		String str[] = temp.split(" ");

		R = Integer.parseInt(str[0]);
		C = Integer.parseInt(str[1]);

		graph = new char[R][C];
		visited = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			temp = br.readLine();
			for (int j = 0; j < C; j++) {
				graph[i][j] = temp.charAt(j);
				if (graph[i][j] == 'D') {
					finish_point = new Pos(i, j);
				} else if (graph[i][j] == 'S') {
					curr_point = new Pos(i, j, 0);
					visited[i][j] = true;
				} else if (graph[i][j] == '*') {
					water_list.addLast(new Pos(i, j));
				}
			}
		}

		DFS(curr_point.x, curr_point.y, 0);
		
		if (!flag)
			System.out.println("KAKTUS");

	}

	public static void DFS(int x, int y, int time) {
		if (flag)
			return;
		water();
		visited[x][y] = true;
		
		if (x == finish_point.x && y == finish_point.y) {
			System.out.println(time);
			flag = true;
			return;
		}
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];

			if (nx < 0 || nx >= R || ny < 0 || ny >= C)
				continue;
			if (graph[nx][ny] == 'X' || graph[nx][ny] == '*' || visited[nx][ny])
				continue;

			DFS(nx, ny, time + 1);
		}
		// 물 움직이기(?)

		visited[x][y] = false;
	}

	public static void water() {
		// 물의 이동
		while (!water_list.isEmpty()) {
			Pos now = water_list.pollFirst();
			for (int d = 0; d < 4; d++) {
				
				int nx = now.x + dx[d];
				int ny = now.y + dy[d];
				
				if (nx < 0 || nx >= R || ny < 0 || ny >= C)
					continue;
				if (graph[nx][ny] == 'X' || graph[nx][ny] == 'D')
					continue;
				graph[nx][ny] = '*';
			}
		} // while문 종료

		water_list.clear();
		
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (graph[i][j] == '*') {
					water_list.addLast(new Pos(i, j));
				}
			}
		}
	}

}// main 종료

cih468 4년 전 0

저는 bfs로 짰었는데 같은 문제로 고민하다가 해결했습니다.

이미 방문한 위치를 굳이 dfs의 재귀함수에 들어가서 다시 확인하게 되서 생기는 문제로 보이네요.

visited배열로 방문한 위치를 확인하는 부분을 재귀함수의 앞쪽에서 확인이 아니라 재귀함수dfs에 들어가기 전에 확인해주면 해결됩니다.

70번 줄에 있는 visited[x][y] = true;를

dfs에 들어가기 전인 85번 라인으로 옮겨주면 해결될것 같네요

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

문제

문제

출처

ICPC

메모리초과

syoungee 4년 전 0

cih468 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말