Softeer 7594번
https://softeer.ai/practice/7594

문제

---

생각하기

---

• 백트래킹을 통해서 경우의 수를 계산하면 된다.

동작

처음에 DFS로 일반적인 4가지 방향 백트래킹을 구현했는데, 고민을 하다보니 전체를 탐색하면서 아래와 오른쪽으로만 이동하게 탐색하는 것 만으로도 충분히 쌍을 만들 수 있다는 것을 파악했다.

또한 기존에 내가 구현하던 DFS로는 모두 연결된 쌍만 구현이 된다고 생각했는데 DFS내에서 2차원 반복문으로 map전체를 탐색하게 하니 떨어져 있는 쌍도 만들어서 경우의 수를 계산할 수 있었다.

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(isVisited[i][j]) continue;
                
                for(int k=0; k<2; k++) {
                    int nextX = dirX[k] + i;
                    int nextY = dirY[k] + j;

                    if(!isAble(nextX, nextY)) continue;

                    isVisited[i][j] = true;
                    isVisited[nextX][nextY] = true;
                    DFS(depth + 1, sum + map[i][j] + map[nextX][nextY], maxDepth);
                    isVisited[i][j] = false;
                    isVisited[nextX][nextY] = false;
                }  
            }
        }

결과

코드

---

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

public class Main {
    // input
    private static BufferedReader br;

    // variables
    private static int N, ans;
    private static int[][] map;
    private static boolean[][] isVisited;
    private static final int[] dirX = {0, 1};
    private static final int[] dirY = {1, 0};
    
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        input();
        
        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int maxDepth = 4;
        if(N == 2) {
            maxDepth = 2;
        }
        
        DFS(0, 0, maxDepth);

        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static void DFS(int depth, int sum, int maxDepth) {
        if(depth == maxDepth) {
            ans = Math.max(ans, sum); 
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(isVisited[i][j]) continue;
                
                for(int k=0; k<2; k++) {
                    int nextX = dirX[k] + i;
                    int nextY = dirY[k] + j;

                    if(!isAble(nextX, nextY)) continue;

                    isVisited[i][j] = true;
                    isVisited[nextX][nextY] = true;
                    DFS(depth + 1, sum + map[i][j] + map[nextX][nextY], maxDepth);
                    isVisited[i][j] = false;
                    isVisited[nextX][nextY] = false;
                }  
            }
        }
    } // End of DFS()

    private static boolean isAble(int nextX, int nextY) {
        return nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && !isVisited[nextX][nextY];
    } // End of isAble()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        ans = -1;

        map = new int[N][N];
        isVisited = new boolean[N][N];
        
        for(int i=0; i<N; i++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    } // End of input()
} // End of Main class