글 읽기 - 고수님들 도와주세요ㅠㅠㅠㅠㅠ

jgjg7882 3년 전 0

각 체스 말에 대해 갈 수 있는 경로를 셋팅해주고 폴로이드 와샬 알고리즘 이용하여 푸는 방식으로 접근했습니다.

문제 예제 답은 다 동일하게 나오는데 뭐가 문제일까요? ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 987654321
#define MAX 11
#define KNIGHT 0
#define BISHOP 1
#define LOOK 2
using namespace std;
typedef pair<int, int> pii; // first: 비용 second: 체스 말 바꾼 횟수
struct cs { int c, r, t, p;}; // c: 비용 r: 체스 말 바꾼 횟수 t: 타입(KNIGHT,BISHOP,LOOK) p: 순서번호
struct cmp {
	bool operator()(const cs& a, const cs& b) {
		if (a.c == b.c)
			return a.r > b.r;
		return a.c > b.c;
	}
};
int n;
int arr[MAX*MAX];
pii visited[MAX*MAX][MAX*MAX][3];
int dist[MAX*MAX][MAX*MAX][3];


void knight_d() {
	int dx[8] = { 1,2,2,1,-1,-2,-2,-1};
	int dy[8] = { -2,-1,1,2,2,1,-1,-2};

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 8; k++) {
				int xx = j + dx[k], yy = i + dy[k];
				if (xx >= 0 && xx < n && yy >= 0 && yy < n) {
					dist[i*n + j][yy*n + xx][KNIGHT] = 1;
				}
			}
		}
}

void bishop_d() {
	int dx[4] = { 1,1,-1,-1 };
	int dy[4] = { -1,1,1,-1 };

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 4; k++) {
				int xx = j + dx[k], yy = i + dy[k];
				while (xx >= 0 && xx < n && yy >= 0 && yy < n) {
					dist[i*n + j][yy*n + xx][BISHOP] = 1;
					xx += dx[k]; yy += dy[k];
				}
			}
		}
}

void look_d() {
	int dx[4] = { 0,1,0,-1 };
	int dy[4] = { -1,0,1,0 };

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < 4; k++) {
				int xx = j + dx[k], yy = i + dy[k];
				while (xx >= 0 && xx < n && yy >= 0 && yy < n) {
					dist[i*n + j][yy*n + xx][LOOK] = 1;
					xx += dx[k]; yy += dy[k];
				}
			}
		}
}

void init() {
	for (int i = 0; i < n*n; i++)
		for (int j = 0; j < n*n; j++) {
			if (i == j)dist[i][j][KNIGHT] = dist[i][j][BISHOP] = dist[i][j][LOOK] = 0;
			else dist[i][j][KNIGHT] = dist[i][j][BISHOP] = dist[i][j][LOOK] = INF;
		}
	knight_d();
	bishop_d();
	look_d();
}

void floyd() {
	for (int k = 0; k < n*n; k++)
		for (int i = 0; i < n*n; i++)
			for (int j = 0; j < n*n; j++) {
				if (i == k || j == k || i == j)continue;
				for (int p = 0; p < 3; p++)
					if (dist[i][j][p] > dist[i][k][p] + dist[k][j][p])
						dist[i][j][p] = dist[i][k][p] + dist[k][j][p];
			}
}

void solve(){
	floyd();
	priority_queue<cs, vector<cs>, cmp> q;
	q.push({ 0,0,KNIGHT,1 }); q.push({ 0,0,BISHOP,1 }); q.push({ 0,0,LOOK,1 });

	while (!q.empty()) {
		cs c = q.top(); q.pop();
		if (c.p == n * n) {
			cout << c.c << " " << c.r << "\n";
			break;
		}
		int v = arr[c.p], e = arr[c.p + 1];
		int dr[3] = { 1,1,1 }; // 추가 변경 횟수
		int dc[3] = { 1,1,1 }; // 추가 시간
		dr[c.t] = dc[c.t] = 0;

		int cost[3] = { c.c + dc[KNIGHT] + dist[v][e][KNIGHT] ,
		c.c + dc[BISHOP] + dist[v][e][BISHOP] , c.c + dc[LOOK] + dist[v][e][LOOK] };
		int rotate[3] = { c.r + dr[KNIGHT],
			 c.r + dr[BISHOP],c.r + dr[LOOK] };

        // 전에 저장했던 경로보다 비용이 저렴하거나 말을 바꾼 횟수가 더 적다면
		if (visited[v][e][KNIGHT].first == 0 || visited[v][e][KNIGHT].first > cost[KNIGHT] ||
			(visited[v][e][KNIGHT].first == cost[KNIGHT] && visited[v][e][KNIGHT].second > rotate[KNIGHT])) {
			q.push({ cost[KNIGHT], rotate[KNIGHT],KNIGHT,c.p + 1 });
			visited[v][e][KNIGHT] = { cost[KNIGHT], rotate[KNIGHT]};
		}
        
		if (visited[v][e][BISHOP].first == 0 || visited[v][e][BISHOP].first > cost[BISHOP] ||
			(visited[v][e][BISHOP].first == cost[BISHOP] && visited[v][e][BISHOP].second > rotate[BISHOP])) {
			q.push({ cost[BISHOP], rotate[BISHOP],BISHOP,c.p + 1 });
			visited[v][e][BISHOP] = { cost[BISHOP], rotate[BISHOP] };
		}
        
		if (visited[v][e][LOOK].first == 0 || visited[v][e][LOOK].first > cost[LOOK] ||
			(visited[v][e][LOOK].first == cost[LOOK] && visited[v][e][LOOK].second > rotate[LOOK])) {
			q.push({ cost[LOOK], rotate[LOOK],LOOK,c.p + 1 });
			visited[v][e][LOOK] = { cost[LOOK], rotate[LOOK] };
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	init();
	for(int i=0; i<n; i++)
		for (int j = 0; j < n; j++) {
			int od;
			cin >> od;
			arr[od] = i * n + j;
		}
	solve();
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

고수님들 도와주세요ㅠㅠㅠㅠㅠ

jgjg7882 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말