Softeer Lv3 - 함께하는 효도

문제

https://softeer.ai/app/assessment/index.html?xid=90203&xsrfToken=7hjE55UE6Y45xwU1wgUihTTAMos0vMlv&testType=practice

Candidate | Softeer Assessment UI

풀이 시간 : 120분

시도횟수 : 4

복기

소프트티어 첫문제이다. 입력을 어떻게 받는지 꽤 해맸다..

알고보니 백준의 Scanner 입력방식과 동일했고, 오랜만이라 어떻게 입력받는지 고민하다가 시간을 또 썼다.

 

문제는 백트래킹 + 순열 이다.

백트래킹을 구현했는데, 제출하니 실패란다.. 틀린 풀이방법이 아니라 부분점수가 있을줄알았는데 왜 없지..? 했는데 세부 내역을 보니 3번 테케가 틀렸다. 왜 틀렸는지 고민을 했고, 어느 친구부터 시작하느냐에 따라 결과값이 달라진다는걸 빠르게 캐치했다. 순열과 조합.. 이것도 다 오랜만에 하니 기억이 흐릿흐릿하다보니 구현하는데 시간을 꽤 썼다.

 

만약 시험이고, 세부 테케가 주어지지 않았다면 나는 틀렸을것이다.

떠오른 풀이로 즉각적으로 구현하지 말고, 풀이 기준으로 예제를 돌려가면서, 검증한 뒤 풀었으면 좀 더 더 빠르게 풀었을것 같다. 

그리고 쓸데없는 전역변수들을 너무 많이 선언했고, 변수명도 즉각적으로 떠오른 걸로 지어서 코드가 다소 조잡해 보인다.. 이런 부분도 개선하면 좋겠다.

 

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

public class Main {

    private static int MAX = 0;
    private static int N, M;
    private static int[][] MAP;
    private static int[][] SUBMAP;
    private static boolean[][] visited;
    private static int[][] freinds;
    private static boolean[] freindsPeek;
    private static List<List<Integer>> permutation;
    private static int[] dx = {0,1,-1,0};
    private static int[] dy = {1,0,0,-1};
    private static Deque<Point> points;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        MAP = new int[N][N];
        visited = new boolean[N][N];
        
        sc.nextLine();
        for(int i = 0 ; i < N ; i++) {
            String[] nums = sc.nextLine().split(" ");
            for(int j = 0 ; j < N ; j++) {
                MAP[i][j] = Integer.parseInt(nums[j]);
                visited[i][j] = false;
            } 
        }

        freinds = new int[M][2];
        freindsPeek = new boolean[M];
        for(int i = 0 ; i < M ; i++){
            int x = sc.nextInt()-1;
            int y = sc.nextInt()-1;
            freinds[i][0] = x;
            freinds[i][1] = y;
        }

        permutation = new ArrayList<>();
        getPerm(0, new LinkedList<>());
        int answer = 0;
        for(List<Integer> perm : permutation) {
            int sum = 0;
            SUBMAP = new int[N][N];
            for(int i = 0 ; i < N ; i++){
                for(int j = 0 ; j < N ; j++){
                    SUBMAP[i][j] = MAP[i][j];
                }
            }
            for(Integer num : perm) {
                MAX = 0;
                int x = freinds[num][0];
                int y = freinds[num][1];
                Deque<Point> load = new LinkedList<>();
                load.addLast(new Point(x, y));
                visited[x][y] = true;
                dfs(x, y, 0, SUBMAP[x][y], load);
                visited[x][y] = false;
                load.pollLast();
                sum += MAX;
               // System.out.println(MAX);
                for(Point p : points) {
                    // System.out.println(p.x + "," + p.y);
                    SUBMAP[p.x][p.y] = 0;
                }
            }
            if(answer < sum) {
                answer = sum;
            }
        }
        

        System.out.println(answer);
    }

    static void getPerm(int cnt, Deque<Integer> perm){
        if(cnt == M) {
            List<Integer> indexs = new ArrayList<>();
            for(Integer num : perm){
                indexs.add(num);
            }
            
            permutation.add(indexs);
            return;
        }

        for(int i = 0 ; i < M ; i++){
            if(freindsPeek[i]){
                continue;
            }

            freindsPeek[i] = true;
            perm.addLast(i);
            getPerm(cnt + 1, perm);
            perm.pollLast();
            freindsPeek[i] = false;
        }
    }
    
    static void dfs(int x, int y, int count, int sum, Deque<Point> load) {
        if(count == 3){
            if(sum > MAX) {
                points = new LinkedList<>();
                for(Point p : load){
                    points.addLast(new Point(p.x, p.y));
                }
                MAX = sum;
            }
            return;
        }
        
        for(int i = 0 ; i < 4 ; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx >= N || ny < 0 || ny >= N || visited[nx][ny]) {
                continue;
            }
            load.addLast(new Point(nx, ny));
            visited[nx][ny] = true;
            dfs(nx, ny, count + 1, sum + SUBMAP[nx][ny], load);
            visited[nx][ny] = false;
            load.pollLast();
        }
    }

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}