글 읽기 - 백트래킹 접근법

jkh9615 3년 전 0

안녕하세요!

우선 DFS로 풀이시 풀이시 TLE가 나오는것은 알고있습니다.

요즘은 백트래킹파트를 공부중이여서 백트래킹으로 한번 접근해봤습니다.

(예상은 했지만 역시나) 백트래킹으로 접근해도 TLE가 나오더군요.

해당 부분은 DFS와 BFS의 특성때문에 어쩔 수 없다고 생각합니다.!

제가 궁금한것은 '(제한사항을 무시하고) 백트래킹으로 해당 문제를 이렇게 푸는게 맞는지?' 입니다.

(예제 입력와 게시판에 있는 반례 등에서는 모두 정답이였습니다!)

위에서 말했다시피 요즘 백트래킹을 연습중이여서 문득 궁금해서 올려봅니다!

import java.util.*;
import java.io.*;
public class Main {
	static int n, m;
	static int[][] map;
	static boolean[][] visit;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String fLine = br.readLine();
		n = stoi(fLine.split(" ")[0]);
		m = stoi(fLine.split(" ")[1]);
		map = new int [n+1][m+1];
		visit = new boolean[n+1][m+1];
		
		for(int i = 1; i <= n; i++) {
			String str = br.readLine();			
			for(int j = 1; j <= m; j++)
				map[i][j] = str.charAt(j-1)-'0';
		}
		
		visit[1][1] = true;
		DFS(1, 1, 0, 1);
		
		if(min == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(min);
	}
	
	public static void DFS(int p, int q, int breakCnt, int moveCnt) {
		if(p == n && q == m) {
			if(moveCnt < min)
				min = moveCnt;	
		}else {
			for(int i = 0; i < 4; i++) {
				int newx = p + dir[i][0];
				int newy = q + dir[i][1];				
				if(newx > 0 && newy > 0 && newx <= n && newy <= m) {
					//유효한 경로인지부터 확인
					if(!visit[newx][newy]) {
						//방문을 안 한 경우에만 방문해야겠음.
						if(map[newx][newy] == 1) {
							//벽이라면
							if(breakCnt == 0) {
								//처음 부수는 경우만 부숨
								visit[newx][newy] = true;
								DFS(newx,newy,breakCnt+1,moveCnt+1); //벽을 1회 부수고 다시 DFS
								visit[newx][newy] = false;
							}
						}else {
							//벽이 아니라면
							visit[newx][newy] = true;
							DFS(newx,newy,breakCnt,moveCnt+1); //벽을 부수지 않고 다시 DFS
							visit[newx][newy] = false;
						}
					}
				}
			}
		}
	}
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}

}

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

문제

문제

출처

ICPC

백트래킹 접근법

jkh9615 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말