[소프티어] 함께하는 효도 - Java

문제

---

https://softeer.ai/practice/7727

Softeer - 현대자동차그룹 SW인재확보플랫폼

• 소요 시간 : 1시간
• 난이도 : LV 3

나의 풀이

---

 

접근 방법

DFS + 백트래킹을 이용한다.

1. 친구들 순서대로 반복

1-1. 3초동안 이동하며 열매를 수확한다. 이때 DFS를 돌려서 갈 수 있는 모든 경우의 수를 탐색한다. 

1-2. 3초가 되었으면 다음 친구의 수확을 반복한다. 

2. 모든 친구들이 수확을 완료했다면 답을 갱신한다. 

시간복잡도

m명의 친구가 있고 (m) -> 각 친구마다 3초동안 이동해야 하고 -> 각 위치에서 4방향 선택 가능 (상하좌우)
따라서 각 친구마다 4³회의 탐색 가능하다. (최악의 경우)
전체 시간복잡도: O(m * 4³) (m은 친구 수, 1 ≤ m ≤ 3)

코드

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

public class Main {

    private static int n;
    private static int m;
    private static int[][] map;
    private static boolean [][] visited;
    private static int[][] friends;
    private static int answer;
    private static int[] dy = {0, 1, 0, -1};
    private static int[] dx = {1, 0, -1, 0};

    public static boolean inRange(int x, int y) {
        return (0 <= x && x < n) && (0 <= y && y < n);
    }
    
    public static void dfs(int friendIdx, int x, int y, int fruits, int visitCnt) {
        if (visitCnt == 3) {
            if (friendIdx == m-1 && answer < fruits) {
                answer = fruits;
                
            } else if (friendIdx < m-1) {
                int x2 = friends[friendIdx+1][0];
                int y2 = friends[friendIdx+1][1];

                visited[x2][y2] = true;
                dfs(friendIdx+1, x2, y2, fruits + map[x2][y2], 0);
            }
            return;
        } else {
            for(int i=0; i<4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];

                if (!inRange(nx, ny) || visited[nx][ny])
                    continue;

                visited[nx][ny] = true;
                dfs(friendIdx, nx, ny, fruits + map[nx][ny], visitCnt + 1);
                visited[nx][ny] = false;
            }
        }
        
        return;
    }
    public static void main(String[] args) throws IOException {

        // input
        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][n];
        visited = new boolean[n][n];
        
        friends = new int[m][2];
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()); 
            }
        }

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            friends[i][0] = Integer.parseInt(st.nextToken())-1; 
            friends[i][1] = Integer.parseInt(st.nextToken())-1; 
        }        

        int x = friends[0][0];
        int y = friends[0][1];
        visited[x][y] = true;
        dfs(0, x, y, map[x][y], 0);

        System.out.print(answer);
    }
}

 

결과 : 정답

 

정리

---

드디어 DFS + 백트래킹에 조금 익숙해졌다..

다른 분들 풀이를 보니까 Point라는 클래스를 만들어서 사용하기도 하던데, 비슷하게 해봐야겠다.