[ day 9 ] 격자 위의 ELICE

격자 위의 ELICE

• 시간 제한: 7초

엘리스는 N×N 격자 모양의 미로에 갇혀버렸다! 가장 왼쪽 위 칸의 좌표는 (1,1)이고 가장 오른쪽 아래 칸의 좌표는(N,N)이다.

엘리스는 위대한 마법사이기 때문에 미로 위에 흩어져 있는 글자들을 순서대로 모아 단어 ELICE를 만든다면, 그 자리에서 즉시 순간 이동 마법을 이용해 미로를 탈출할 수 있다고 한다. 엘리스는 현재 (1,1)에 위치해 있다.

모든 격자에는 양의 정수가 쓰여 있다. 몇몇 칸에는 글자가 놓여 있을 수 있다. 엘리스가 있는 칸에 글자가 놓여 있는 경우, 원한다면 그 글자를 얻을 수 있다. 글자를 얻는다면 다시 이 칸에 도달해도 다시 한번 글자를 얻을 수는 없다.
이렇게 모은 글자를 얻은 순서대로 이었을 때, 단어 ELICE가 된다면 순간 이동 마법을 사용할 수 있다.

엘리스가 어떠한 격자 칸에서 다른 격자 칸으로 이동하고 싶다면, 상하좌우 한 방향을 골라 인접한 격자 칸으로 이동할 수 있다. (단 미로를 벗어날 수는 없다.)
엘리스가 어떤 칸에서 인접한 칸으로 이동할 때, 두 칸 위에 쓰여 있는 정수의 합만큼의 시간이 걸린다.

예를 들어 아래 예제1과 같이 3이 쓰여 있는 (1,2)격자에서 4가 쓰여 있는 (1,3)격자로 이동하려면 7의 단위 시간이 필요하다.

미로에는 정확히 2개의 E와, 1개의 L, 1개의 I, 1개의 C문자가 존재한다. 엘리스가 순간 이동을 마법을 사용해 미로를 탈출하는 최소 단위 시간을 알려주자.

 

지시사항

입력

• 첫째 줄에 정수 N이 주어진다.

3≤N≤1000

• 둘째 줄부터 N+1번째 줄까지 ai,j​가 주어진다.
• • i+1번째 줄에 들어오는 j번째 정수는 ai,j​이고, 격자 (i,j)에 쓰여있는 정수를 의미한다.

1≤ai,j​≤1000

• N+2번째 줄부터 N+6번째 줄까지는 정수 r, c가 주어진다.
• • 각 줄에 주어지는 정보는, 격자 (r,c)에 순서대로 글자 E, L, I, C, E가 놓여있음을 의미한다.

1≤r,c≤N

• • N+2번째 줄에 입력된 위치의 E와 N+6번째 줄에 입력된 위치의 E는 프로그램 내에서 동일한 글자로 취급한다.

출력

• 첫째 줄에 엘리스가 미로를 탈출하는 최소 단위 시간을 출력한다.

입력 예시

3
2 3 4
1 4 3
1 1 1
1 1
2 1
3 1
3 2
3 3

출력 예시

9

 

 

정답 코드

C++

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll n_ = 2e6 + 100, inf = (ll)1e9 * (ll)1e9 + 7;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, ans;
ll gcd(ll x, ll y) {
	if (!y)return x;
	return gcd(y, x % y);
}
ll A[n_], dist[n_][5];
vector<P>v[n_], elice;
ll get(ll y, ll x) {
	return y * n + x;
}
void solve() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> a;
			int idx = get(i, j);
			A[idx] = a;
		}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int now = get(i, j);
			//cout << now << ' ';
			for (int k = 0; k < 4; k++) {
				y = i + dy[k], x = j + dx[k];
				if (y < 0 || y >= n || x < 0 || x >= n)continue;
				int nxt = get(y, x);
				v[now].push_back({ nxt,A[now] + A[nxt] });
			}
		}
		//cout << endl;
	}
	for (int i = 0; i < 5; i++) {
		cin >> y >> x;
		y--, x--;
		elice.push_back({ y,x });
	}
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < n_; j++)dist[j][i] = inf;
		y = elice[i].first, x = elice[i].second;
		priority_queue<P, vector<P>, greater<>>pq;
		ll now = get(y, x);
		dist[now][i] = 0;
		pq.push({ 0,now });
		while (pq.size()) {
			a = pq.top().first, b = pq.top().second;
			pq.pop();
			if (dist[b][i] < a)continue;
			for (auto nxt : v[b]) {
				if (dist[nxt.first][i] > nxt.second + a) {
					dist[nxt.first][i] = nxt.second + a;
					pq.push({ nxt.second + a,nxt.first });
				}
			}
		}
	}
	sum = dist[get(0, 0)][0];
	for (int i = 0; i <= 3; i++)sum += dist[get(elice[i + 1].first, elice[i + 1].second)][i];
	ans = sum;
	sum = 0;
	sum = dist[get(0, 0)][4];
	sum += dist[get(elice[1].first, elice[1].second)][4];
	sum += dist[get(elice[2].first, elice[2].second)][1];
	sum += dist[get(elice[3].first, elice[3].second)][2];
	sum += dist[get(elice[0].first, elice[0].second)][3];
	ans = min(ans, sum);
	cout << ans << endl;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> tc;
	while (tc--)solve();
}

Python

from heapq import heappop, heappush

MAX = 2000100
INF = int(1e18)
dirY = [-1, 0, 1, 0]
dirX = [0, 1, 0, -1]

def get(y, x):
    return y * N + x

N = int(input())
A = [0] * MAX
for i in range(1, N + 1):
    for j, a in enumerate(map(int, input().split()), start=1):
        A[get(i, j)] = a

elice = [tuple(map(int, input().split())) for _ in range(5)]

v = [list() for _ in range(MAX)]

for i in range(1, N + 1):
    for j in range(1, N + 1):
        current = get(i, j)
        for k in range(4):
            y, x = i + dirY[k], j + dirX[k]
            if y < 1 or y > N or x < 1 or x > N:
                continue

            next_ = get(y, x)
            v[current].append((A[current] + A[next_], next_))

dist = [[INF] * 5 for _ in range(MAX)]

for i in range(5):
    now = get(*elice[i])
    dist[now][i] = 0

    pq = [(dist[now][i], now)]
    while pq:
        curDist, curIndex = heappop(pq)

        for nextDist, nextIndex in v[curIndex]:
            if dist[nextIndex][i] > curDist + nextDist:
                dist[nextIndex][i] = curDist + nextDist
                heappush(pq, (curDist + nextDist, nextIndex))

answer1 = dist[get(1, 1)][0]
for i in range(1, 5):
    answer1 += dist[get(*elice[i])][i - 1]

answer2 = dist[get(1, 1)][4]
answer2 += dist[get(*elice[1])][4]
answer2 += dist[get(*elice[2])][1]
answer2 += dist[get(*elice[3])][2]
answer2 += dist[get(*elice[0])][3]

print(min(answer1, answer2))

Java

import java.util.*;
import java.io.*;
 
public class Main {
    static final int MAX = 2000100;
    static final long INF = (long) 1e18;
    static final int[] dirY = {-1, 0, 1, 0};
    static final int[] dirX = {0, 1, 0, -1};
    static int N;
    static long[] A = new long[MAX];
    static List<List<Pair>> v = new ArrayList<>();
    static long[][] dist = new long[MAX][5];
 
    static class Pair {
        int index;
        long cost;
        Pair(int index, long cost) {
            this.index = index;
            this.cost = cost;
        }
    }
 
    public static int get(int y, int x) {
        return y * N + x;
    }
 
    public static void main(String[] args) {
        FastReader sc = new FastReader();
        N = sc.nextInt();
       
        for (int i = 0; i < MAX; i++) {
            v.add(new ArrayList<>());
        }
       
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                int a = sc.nextInt();
                A[get(i, j)] = a;
            }
        }
 
        List<int[]> elice = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            int y = sc.nextInt();
            int x = sc.nextInt();
            elice.add(new int[]{y, x});
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                int current = get(i, j);
                for (int k = 0; k < 4; k++) {
                    int y = i + dirY[k];
                    int x = j + dirX[k];
                    if (y < 1 || y > N || x < 1 || x > N) {
                        continue;
                    }
                    int next = get(y, x);
                    v.get(current).add(new Pair(next, A[current] + A[next]));
                }
            }
        }
 
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < MAX; j++) {
                dist[j][i] = INF;
            }
            int[] start = elice.get(i);
            int now = get(start[0], start[1]);
            dist[now][i] = 0;
 
            PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingLong(p -> p.cost));
            pq.add(new Pair(now, 0));
 
            while (!pq.isEmpty()) {
                Pair p = pq.poll();
                long curDist = p.cost;
                int curIndex = p.index;
 
                for (Pair next : v.get(curIndex)) {
                    if (dist[next.index][i] > curDist + next.cost) {
                        dist[next.index][i] = curDist + next.cost;
                        pq.add(new Pair(next.index, curDist + next.cost));
                    }
                }
            }
        }
 
        long answer1 = dist[get(1, 1)][0];
        for (int i = 1; i < 5; i++) {
            answer1 += dist[get(elice.get(i)[0], elice.get(i)[1])][i - 1];
        }
 
        long answer2 = dist[get(1, 1)][4];
        answer2 += dist[get(elice.get(1)[0], elice.get(1)[1])][4];
        answer2 += dist[get(elice.get(2)[0], elice.get(2)[1])][1];
        answer2 += dist[get(elice.get(3)[0], elice.get(3)[1])][2];
        answer2 += dist[get(elice.get(0)[0], elice.get(0)[1])][3];
 
        System.out.println(Math.min(answer1, answer2));
    }
 
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}