백준 1029 그림 교환 python, java

gobeul·2023년 10월 3일

Java python 백준 알고리즘 문제

알고리즘 풀이

목록 보기

40/70

외판원순회 문제를 조금 변형한 문제라고 한다.
외판원순회 문제에서 DP차원이 하나 높아졌는데 풀이를 이해하는데 많이 어려웠다.

📜 문제 바로 가기 : 그림 교환

제출코드

파이썬

import sys
input = sys.stdin.readline

from collections import defaultdict

N = int(input())
price = [list(map(int, input().rstrip())) for _ in range(N)]

DP = defaultdict(list)

DP[1] = [[0] * 10 for _ in range(N)]
# DP[x][y][z] = 그림을 소유했던 상황이 x인 상태에서 마지막으로 y가 z원에 그림을 샀을때


def DFS(visit, s, p):
    # visit 그림을 소유했던 사람
    # s 그림을 가지고 있는 사람
    # p 지금 그림 가격
    if DP[visit] == []:
        DP[visit] = [[0] * 10 for _ in range(N)]
    
    if DP[visit][s][p] != 0:
        return DP[visit][s][p]
    
    cnt = 0
    for i in range(N):
        if visit & 1 << i == 0: # vistit에서는 i가 아직 그림을 못만져봄
            if p <= price[s][i]: # p 가격에 s가 i 한테 그림을 팔 수 있음
                cnt = max(cnt, DFS(visit | 1 << i, i, price[s][i]) + 1)
    
    DP[visit][s][p] = cnt
    return cnt

print(DFS(1, 0, 0) + 1)

자바

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.HashMap;


public class Main {
    static int N;
    static int[][] price;
    static HashMap<Integer, int[][]> DP;
    static int DFS(int visit, int s, int p) {
        if (DP.get(visit) == null) {
            DP.put(visit, new int[N][10]);
        }

        if (DP.get(visit)[s][p] != 0) {
            return DP.get(visit)[s][p];
        }

        int cnt = 0;
        for (int i = 0; i < N; i ++) {
            if ((visit & 1 << i) == 0) {
                if (price[s][i] >= p) {
                   cnt = Math.max(cnt, DFS(visit | 1 << i, i, price[s][i]) + 1);
                }
            }
        }

        DP.get(visit)[s][p] = cnt;
        return cnt;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        price = new int[N][N];
        for (int i = 0; i < N; i++) {
            String t = br.readLine();
            for (int j = 0; j < N; j++) {
                price[i][j] = Integer.parseInt(String.valueOf(t.charAt(j)));
            }
        }

        DP = new HashMap<>();

        DP.put(1, new int[N][10]);
        System.out.println(DFS(1, 0, 0) + 1);

    }

}

접근방법

TSP알고리즘이라는 힌트를 얻고도 못 푼이유는 TSP의 경우는 출발점 까지 돌아오는 경로가 반드시 존재했지만 이 문제는 그렇지 않다. 중간에 길이 끊길 수 있으며 그 상황이 답이 될 수 있었기 때문에 DP값을 뭐라고 정의를 해야될지 몰랐다.

DP[x][y][z]

DP[x][y][z] 값은 그림을 소유했던 상황이 x인 상태에서 마지막으로 y가 z원에 그림을 샀을때 그림을 만질 수 있는 최대 사람의 수로 정하고 문제를 풀었다.

이번엔 조금 다르게 DP[x]에 딕셔러리 자료형을 넣어 봤는데 이유는 결국 방문값의 모든 경우의 수를 확인하기 위해 배열을 미리 만들어야한다면 2**N 개의 2차원 배열을 만들어줘야한다. 이러한 부분이 낭비될 수 있다고 생각이 들어 딕셔너리 형태로 필요할때만 만들어 줘봤다.

맨 아래가 딕셔너리를 썼을때 (위 코드)
맨 위가 DP = [[[0] * 10 for _ in range(N)] for _ in range(1 << N)] 이 방법으로 모든 방문 배열값을 만들어 줬을때다.

동일 코드에서 메모리와 시간이 더 감소했다.

일반적인 TSP와 뭐가 다를까

DP차원이 3차원으로 늘었다는게 가장 큰 차이이다.
전에 풀었던 외판원 순회 문제를 복기해보면 DP[i][visit]값으로 현재 위치가 i 이고 방문한 상태가 visit 일때 현 위치에서 출발점 까지 갈 수 있는 가장 짧은 거리를 주었다.

그러면 이 문제도 DP[i][visit]에 현재 그림을 가지고 있는 사람이 i, 그림을 만져본 상태가 visit 일 때 현 상태에서 그림을 만져 볼 수 있는 사람의 수의 최대값을 넣었으면 안 되었을까??

어?? 뭐지

된다?? 일반 적인 TSP 알고리즘을 적용해도 통과가 된다...

import sys
input = sys.stdin.readline

N = int(input())
price = [list(map(int, input().rstrip())) for _ in range(N)]

PP = [[0] * N for _  in range(1 << N)]

def TSP(v, s, p):
    if PP[v][s] != 0:
        return PP[v][s]
    
    cnt = 0
    for i in range(N):
        if v & 1 << i == 0: # vistit에서는 i가 아직 그림을 못만져봄
            if p <= price[s][i]: # p 가격에 s가 i 한테 그림을 팔 수 있음
                cnt = max(cnt, TSP(v | 1 <<i, i, price[s][i]) + 1)

    PP[v][s] = cnt
    return cnt

print(TSP(1, 0, 0) + 1)