글 읽기 - 시간초과를 어떻게 해결해야할까요? (DFS)

chsong91 4년 전 0

BFS로는 풀었지만 DFS로도 시간초과가 안나게 풀고싶은데

아직 초보라 시간, 메모리관리를 잘 못합니다.. ㅠㅠ

고수님들이 도와주시면 정말 큰 힘이 됩니다. 지적은 달게 받겠습니다 도와주세요!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	private static int n, m;
	private static int[] dx = { 1, -1, 0, 0 };
	private static int[] dy = { 0, 0, 1, -1 };
	private static int min = 987654321;
	private static boolean[][] check;
	private static int[][] a;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		a = new int[n][m];
		check = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for (int j = 0; j < m; j++) {
				a[i][j] = str.charAt(j) - 48;
			}
		}
        
//		System.out.println(BFS(new Point(0, 0), 0));
//		check = new boolean[n][m];
		DFS(new Point(0, 0), 0, check);
		System.out.println(min);
		br.close();
        
	}
	/*
	public static int BFS(Point start, int count) { // bfs
		count++;
		Queue<Point> qu = new LinkedList<Point>();
		check[start.x][start.y] = true;
		qu.add(start);
		while (!qu.isEmpty()) {
			int size = qu.size();
			for (int i = 0; i < size; i++) {
				Point now = qu.poll();
				if (now.x == n - 1 && now.y == m - 1)
					return count; // 도착지점이면 종료
				for (int j = 0; j < 4; j++) {
					int nx = now.x + dx[j];
					int ny = now.y + dy[j];
					if (nx < 0 || ny < 0 || nx >= n || ny >= m || check[nx][ny] || a[nx][ny] == 0)
						continue;
					check[nx][ny] = true;
					qu.add(new Point(nx, ny));
				}
			}
			count++;
		}
		return -1;
	}
	*/
	
	public static void DFS(Point start, int count, boolean[][] check) { // dfs
		count++;
		check[start.x][start.y] = true;
		if(count >= min) return; // count가 min보다 크면 더이상 탐색이 무의미하니까 종료
		if (start.x == n - 1 && start.y == m - 1) { // 도착지점이면 종료
			min = Math.min(min, count);
			return;
		}
		for (int i = 0; i < 4; i++) {
			int nx = start.x + dx[i];
			int ny = start.y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || check[nx][ny] || a[nx][ny] == 0)
				continue;
			DFS(new Point(nx,ny), count, check);
			check[nx][ny] = false; // undo 
		}
	}
	

	public static class Point {
		private int x, y;

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

dyk777 4년 전 1

DFS는 최단거리를 구하는 데에 쓸 수 없고, 설령 특정 가능한 경우가 있다고 하더라도 매우 어려운 처리를 필요로 합니다.

chsong91 4년 전 0

dky777님 답변 감사합니다.

이 문제를 dfs로 풀 날이 오기를 기대하며 열심히 노력하겠습니다.

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

문제

문제

출처

ICPC

시간초과를 어떻게 해결해야할까요? (DFS)

chsong91 4년 전 0

dyk777 4년 전 1

chsong91 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말