백준 14500 테트로미노 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/14500

풀이는 다음과 같다.

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

public class Main {
    static int[][] map;
    static int R, C;
    static int[] dr = {-1, 1, 0, 0}; //상하좌우 순
    static int[] dc = {0, 0, -1, 1};
    static boolean[][] visited;
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //모양에 집착할 필요가 없다. DFS 무작위로 4방향으로 뻗어나가게 두면 그게 테트로미노의 전체 모양이 된다.

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st1.nextToken());
        C = Integer.parseInt(st1.nextToken());
        map = new int[R][C];
        visited = new boolean[R][C];

        for(int r = 0 ; r < R ; r++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int c = 0 ; c < C ; c++) {
                map[r][c] = Integer.parseInt(st2.nextToken());
            }
        }
        
        //여기까지 초깃값 세팅

        for(int r = 0 ; r < R ; r++) {
            for(int c = 0 ; c < C ; c++) {
                visited[r][c] = true; //여기와 아래의 visited[r][c] = false; 이해하기
                backTracking(r, c, 1, map[r][c]);
                visited[r][c] = false;
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();

    }

    //시작점부터 무작위로 4개씩 뻗어나가 그 4개의 합을 구하는 DFS
    //backTracking(r, c, depth+1, sum + map[nextR][nextC]);
    //backTracking(nextR, nextC, depth+1, sum + map[nextR][nextC]); 이 둘의 차이를 이해하면 쉬움.
    static void backTracking(int r, int c, int depth, int sum) { //sum은 map[r][c]가 초깃값, depth는 초깃값 1

        if(depth == 4) {
            if(answer < sum) answer = sum;
            return;
        }

        for(int i = 0 ; i < 4 ; i++) {
            int nextR = r + dr[i];
            int nextC = c + dc[i];

            if(!isValid(nextR, nextC)) continue; //index 유효하지 않으면 다음 i
            if(visited[nextR][nextC]) continue;



            if(depth == 2) { //ㅗ 만들어줘야 할 경우 (두번째 칸에서 엇나가야지 그래서 depth 2),
                visited[nextR][nextC] = true;
                backTracking(r, c, depth+1, sum + map[nextR][nextC]);
                visited[nextR][nextC] = false;
            }

            visited[nextR][nextC] = true;
            backTracking(nextR, nextC, depth+1, sum + map[nextR][nextC]);
            visited[nextR][nextC] = false;
        }
    }

    static boolean isValid(int r, int c) { //행열의 index가 유효한지 검증
        if(r < 0 || r >= R || c < 0 || c >= C) return false;
        return true;
    }

}

DFS와 백트래킹을 잘 이해하고 있다면, 어렵지 않다.
백트래킹을 잘 모르겠다면,
https://www.acmicpc.net/problem/15649
https://www.acmicpc.net/problem/15650
이 문제들을 풀어보도록 하자.

문제 풀때, 로직은 잘 떠올렸다.
가장 먼저, 각 점을 잡고,
각 점마다 만들 수 있는 테트리스 모양 (아래)

을 DFS, 백트래킹으로 만든다.
해당 모양의 숫자의 합의 최댓값을 구한다.
라고 생각하고 풀었더니,
테스트케이스를 통과하지 못했다.

골똘히 생각했고, 어디서 문제가 나왔냐?

저기 위의 그림중 다섯번째, ㅗ모양을 5번이라고 하자.
내가 지금 있는 위치에서 곧바로 다음 위치로 간다 라고 하면
5번 이외의 모양은 만들 수 있다.
예를 들어 일자 모양을 들면,

ㅁ -> ㅁㅁ -> ㅁㅁㅁ -> ㅁㅁㅁㅁ

(1 -> 2 -> 3 -> 4)
이런식으로 이전에 만들어진 칸에서 다음 칸으로 딱 한칸만! 이동하며 만들 수 있다
하지만, 5번 모양을 생각해 보면,

ㅁ -> ㅁㅁ ->  ㅁㅁ -> ㅁㅁㅁ(4)
			 (3)ㅁ      ㅁ

3번 블럭에서 4번 블럭을 만들기 위해서는, 단순히 상하좌우 이동 한번만으로 만들 수 없다.
3번에서 위로, 거기서 옆으로 가야지,
즉 두번을 움직여야지 만들 수 있다.


이 말이 이해가 간다면, 해당 문제를 해결하기 위해

if(depth == 2) { //ㅗ 만들어줘야 할 경우 (두번째 칸에서 엇나가야지 그래서 depth 2),
                visited[nextR][nextC] = true;
                backTracking(r, c, depth+1, sum + map[nextR][nextC]);
                visited[nextR][nextC] = false;
            }
            
            
//backTracking(r, c, depth+1, sum + map[nextR][nextC]);
//backTracking(nextR, nextC, depth+1, sum + map[nextR][nextC]); 
위 둘의 차이를 이해하면 쉬움.

이 코드를 추가했다.


음.. 읽어봤는데도 나는 도통 무슨말인지 진짜 모르겠다 싶으면,

//backTracking(r, c, depth+1, sum + map[nextR][nextC]);
//backTracking(nextR, nextC, depth+1, sum + map[nextR][nextC]); 

매서드를 보며 위 둘의 로직 차이만 이해하면 될 것 같다.


PS. 골드 4인 이유는 depth == 2일때의 예외때문인 것 같다.
처음의 틀린 코드는 아래와 같이 depth == 2일때의 예외를 생각하지 못했다.

//시작점부터 무작위로 4개씩 뻗어나가 그 4개의 합을 구하는 DFS
    static void backTracking(int r, int c, int depth, int sum) { //sum은 map[r][c]가 초깃값, depth는 초깃값 1
        if(depth == 4) {
            if(answer < sum) answer = sum;
            return;
        }

        for(int i = 0 ; i < 4 ; i++) {
            if(visited[r][c]) continue;
            visited[r][c] = true;
            if(!isValid(r + dr[i], c + dc[i])) continue; //index 유효하지 않으면 다음 i
            backTracking(r + dr[i], c + dc[i], depth+1, sum + map[r + dr[i]][c + dc[i]]);
            visited[r][c] = false;
        }
    }