글 읽기 - 어디가 문제일까요? DFS + DP방식입니다

calgarylof 2년 전 0

반례 확인하고 코드 수정하고 반복하다보니 짬뽕이 되어버렸네요..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static final int INF = Integer.MAX_VALUE;
	
	static int N;
	static int M;

	static int answer;
	static boolean hasCycle;
    
	static char[][] board;
	static int[][] dp;
	static boolean[][] visited;
	
	static int[] my = { -1, 1, 0, 0 }; /* 상, 하, 좌, 우 순서 */
	static int[] mx = { 0, 0, -1, 1 };

	private static int solution() {
		dfs(0, 0, 0);
		if(hasCycle) {
			return -1;
		}
		else return answer;
	}
	
	private static void dfs(int y, int x, int move) {
		// 1. 체크 인
		visited[y][x] = true;
		dp[y][x] = move + 1;
		// 2. 목적지인지 확인한다
		if(hasCycle) {
			return;
		}
        if(board[y][x] == 'H') {
			visited[y][x] = false;
			return;
		}
        answer = answer < move ? move : answer;
		// 3. 연결된 부분을 순회한다
		int value = board[y][x] - '0';
		for(int i = 0; i < 4; i++) {
			int nextY = my[i] * value + y;
			int nextX = mx[i] * value + x;
			// 4. 방문 가능한지 확인한다
			if(0 <= nextY && nextY < N && 0 <= nextX && nextX < M) {
				if(visited[nextY][nextX]) {
					hasCycle = true;
					return;
				}
				if(dp[nextY][nextX] != INF) continue;
				// 5. 방문한다
				dfs(nextY, nextX, move + 1);
			}
		}
		// 6. 체크 아웃
		visited[y][x] = false;
	}
	
	private static void init() {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			board = new char[N][M];
			dp = new int[N][M];
			visited = new boolean[N][M];
			for(int[] a : dp) {
				Arrays.fill(a, INF);
			}
			
			for(int y = 0; y < N; y++) {
				String input = br.readLine();
				for(int x = 0; x < M; x++) {
					board[y][x] = input.charAt(x);
				}
			}
			br.close();
			System.out.println(solution());
			return;
		}
		catch(IOException e) {
			e.printStackTrace();
		}
	}
	public static void main(String[] args) {
		init();
		return;
	}
}

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

문제

문제

출처

ICPC

어디가 문제일까요? DFS + DP방식입니다

calgarylof 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말