백준 26153 로하의 농사

https://www.acmicpc.net/problem/26153

26153번: 로하의 농사

알고리즘 분류: 그래프 이론, DFS

 

 

문제 설명

저번 한양대 오픈 콘테스트에 참여했었을 때 눈여겨 보고있었던 문제였는데, 오늘 종강기념으로 풀고자 했다.

먼저 문제를 봤을 때 처음 갔던 곳을 또 가야하는 문제였고, 한번 탐색 후 visited 변수를 다시 원래대로 복구하는

DFS가 맞는 답이라 생각했다.

구현자체는 어렵지 않았다.

DFS를 진행하면서 방향이 다르면 파이프 개수를 2를 빼고 방향이 같으면 1을 빼는 식으로 하면 쉽게 풀린다.

static void DFS(XY start){
        if(visited[start.x][start.y]) return;
        if(start.cnt == 0){
            sum = Math.max(sum, start.sum);
            return;
        }

        for(int i = 0;i<4;i++){
            int nextx = start.x + next_x[i];
            int nexty = start.y + next_y[i];
            if(nextx < 0 || nexty <0|| nextx>=n|| nexty>=m) continue;
            if(nextx == start_x && nexty == start_y) continue;
            visited[start.x][start.y] = true;
            if(start.vector!=-1 && start.vector != i){
                if(start.cnt - 2 >= 0) DFS(new XY(nextx,nexty,i,start.cnt - 2, start.sum + map[nextx][nexty]));
            }
            else{
                DFS(new XY(nextx,nexty,i,start.cnt - 1, start.sum + map[nextx][nexty]));
            }
            visited[start.x][start.y] = false;
        }
    }

하지만 역시나 한번은 틀렸다. 하나씩 빼먹는 나의 성격탓인지 매번 한번은 틀리게 된다.

여기서 놓쳤던 것이 파이프를 다 안 쓰고도 최대가 될 수 있음을 빼먹었다.

이것을 이렇게 고쳐 맞게 되었다.

static void DFS(XY start){
        if(visited[start.x][start.y]) return;
        sum = Math.max(sum, start.sum);
        if(start.cnt == 0){
            return;
        }

        for(int i = 0;i<4;i++){
            int nextx = start.x + next_x[i];
            int nexty = start.y + next_y[i];
            if(nextx < 0 || nexty <0|| nextx>=n|| nexty>=m) continue;
            if(nextx == start_x && nexty == start_y) continue;
            visited[start.x][start.y] = true;
            if(start.vector!=-1 && start.vector != i){
                if(start.cnt - 2 >= 0) DFS(new XY(nextx,nexty,i,start.cnt - 2, start.sum + map[nextx][nexty]));
            }
            else{
                DFS(new XY(nextx,nexty,i,start.cnt - 1, start.sum + map[nextx][nexty]));
            }
            visited[start.x][start.y] = false;
        }
    }

 

전체코드

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


public class Main {
    static class XY{
        int x;
        int y;
        int vector;
        int cnt;
        int sum;

        public XY(int x, int y, int vector, int cnt, int sum){
            this.x = x;
            this.y = y;
            this.vector = vector;
            this.cnt = cnt;
            this.sum = sum;
        }
    }
    static int next_x[] = {1,-1,0,0};
    static int next_y[] = {0,0,1,-1};
    static int n;
    static int m;

    static int map[][];

    static boolean visited[][];
    static int sum;
    static int start_x;
    static int start_y;

    static void DFS(XY start){
        if(visited[start.x][start.y]) return;
        if(start.cnt == 0){
            sum = Math.max(sum, start.sum);
            return;
        }

        for(int i = 0;i<4;i++){
            int nextx = start.x + next_x[i];
            int nexty = start.y + next_y[i];
            if(nextx < 0 || nexty <0|| nextx>=n|| nexty>=m) continue;
            if(nextx == start_x && nexty == start_y) continue;
            visited[start.x][start.y] = true;
            if(start.vector!=-1 && start.vector != i){
                if(start.cnt - 2 >= 0) DFS(new XY(nextx,nexty,i,start.cnt - 2, start.sum + map[nextx][nexty]));
            }
            else{
                DFS(new XY(nextx,nexty,i,start.cnt - 1, start.sum + map[nextx][nexty]));
            }
            visited[start.x][start.y] = false;
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        visited = new boolean[n][m];
        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j<m;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());
        start_x = Integer.parseInt(st.nextToken());
        start_y = Integer.parseInt(st.nextToken());
        int cnt = Integer.parseInt(st.nextToken());
        sum = map[start_x][start_y];
        DFS(new XY(start_x,start_y,-1,cnt,map[start_x][start_y]));
        System.out.println(sum);
    }
}