입력에 들어오는 숫자가 1부터 10이라 문자열로 변환하면 10이 인덱스 크기에 영향을 줄 수 있다.
입력에 숫자가 들어올 때 -1을 빼주기.
쿼리도 인덱스를 맞춰주기 위해 l,r에 각각 1씩 빼주기.
리스트/배열 저장 대신 문자열로 변환해서 set에 저장하기.
간선 크기가 달라서 BFS 대신 다익스트라 사용
파이썬
# defaultdict로 초기값 INF로 저장장
from collections import defaultdict as dd
import heapq as hq
INF = float('inf')
N = int(input())
arr = list(map(lambda x : str(int(x)-1),input().split()))
# operations 인덱스 맞춰주기
M = int(input())
ops = []
for _ in range(M):
a,b,cost = map(int,input().split())
ops.append((a-1,b-1,cost))
# 다익스트라
def di():
# 문자열로 바꿔서 방문처리리
V = dd(lambda : INF)
V[''.join(arr)] = 0
heap = [(0,''.join(arr))]
while heap:
t,string = hq.heappop(heap)
# 내림차순인지 확인하기기
non_desc = True
for i in range(1,N):
if string[i-1] > string[i]:
non_desc = False
break
if non_desc:
return t
# 인덱스 기반
for a,b,cost in ops:
nstring = ''
nt = t+cost
for i in range(N):
if i == b:
nstring += string[a]
elif i == a:
nstring += string[b]
else:
nstring += string[i]
# 갱신 가능하면 힙에 추가
if nt < V[nstring]:
V[nstring] = nt
hq.heappush(heap,(nt,nstring))
return -1
print(di())
문자열이나 튜플로 저장해야하는데, 어짜피 튜플도 수정 불가능해서 문자열로 사용
물통 채우는 문제로 비슷하게 state를 string이나 tuple로 만들어서 저장하는 문제들이 많았는데, BFS에서 간선에 가중치만 추가된 다익스트라 문제.
자바
import java.io.*;
import java.util.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append((char) (Integer.parseInt(st.nextToken()) - 1 + '0'));
}
String startState = sb.toString();
int M = Integer.parseInt(br.readLine());
int[][] ops = new int[M][3];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
ops[i][0] = Integer.parseInt(st.nextToken()) - 1;
ops[i][1] = Integer.parseInt(st.nextToken()) - 1;
ops[i][2] = Integer.parseInt(st.nextToken());
}
System.out.println(di(startState, ops, N));
}
static int di(String startState, int[][] ops, int N) {
HashMap<String, Integer> V = new HashMap<>();
PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> Integer.compare(n1.t, n2.t));
V.put(startState, 0);
pq.offer(new Node(0, startState));
while (!pq.isEmpty()) {
Node cur = pq.poll();
int t = cur.t;
String string = cur.string;
if (V.get(string) < t)
continue;
boolean nonDesc = true;
for (int i = 1; i < N; i++) {
if (string.charAt(i - 1) > string.charAt(i)) {
nonDesc = false;
break;
}
}
if (nonDesc) {
return t;
}
for (int[] op : ops) {
int a = op[0];
int b = op[1];
int cost = op[2];
char[] nchars = string.toCharArray();
char temp = nchars[a];
nchars[a] = nchars[b];
nchars[b] = temp;
String nstring = new String(nchars);
int nt = t + cost;
if (!V.containsKey(nstring) || nt < V.get(nstring)) {
V.put(nstring, nt);
pq.offer(new Node(nt, nstring));
}
}
}
return -1;
}
static class Node {
int t;
String string;
public Node(int t, String string) {
this.t = t;
this.string = string;
}
}
}
arr을 int로 받아서 toString으로 문자열 생성하기
arr을 char로 받아서 new String(arr)로 문자열 생성하기
heap에 넣을 자료타입이 달라서 전달용 Node 클래스 만들기.
문자열 변환에서도 string builder로 만들어서 set char at 사용하거나, char[] 배열 만들어서 스왑하거나 둘 중 하난데, 메서드보단 기본적으로 사용되는 방식으로 구현하기.
defaultdict 구현에서는 containsKey + get을 사용해서 값이 있는 경우에 값 가져오기.
댓글