[C++] 백준 20057 마법사 상어와 토네이도

문제 링크

---

www.acmicpc.net/problem/20057

20057번: 마법사 상어와 토네이도

 

접근 방법

---

 시뮬레이션이나 구현 류의 문제들은 초기 설계를 어떻게 하느냐에 따라 코드 길이가 차이가 많이 날 수 있으니 초반 설계를 잘하는 것이 중요하다. 코드가 길어진다는 것은 구현이 복잡해질 가능성이 높다는 의미이다.

 

1. 상, 하, 좌, 우 방향에 따른 상대적인 좌표와 그 비율을 미리 저장한다.

typedef struct info{
	int x, y, cost;
};

vector<vector<info>> infoV;

void init() {
	// left, right는 요소의 2번째 인자의 부호를 바꿔주면 되고, up, down은 요소의 1번째 인자의 부호를 전환
	// 알파의 비율 부분은 모든 요소 처리 이후 따로 계산 
	infoV.push_back({ {-1,0,1}, {-1,-1,7}, {-2,-1,2}, {-1,-2,10}, {1,0,1}, {1,-1,7}, {2,-1,2}, {1,-2,10}, {0,-3,5} }); //left
	infoV.push_back({ {0,-1,1}, {1,-1,7}, {1,-2,2}, {2,-1,10}, {0,1,1}, {1,1,7}, {1,2,2}, {2,1,10}, {3,0,5} });  //down
	infoV.push_back({ {-1,0,1}, {-1,1,7}, {-2,1,2}, {-1,2,10}, {1,0,1}, {1,1,7}, {2,1,2}, {1,2,10}, {0,3,5} });   //right
	infoV.push_back({ {0,-1,1}, {-1,-1,7}, {-1,-2,2}, {-2,-1,10}, {0,1,1}, {-1,1,7}, {-1,2,2}, {-2,1,10}, {-3,0,5} }); // up
}

 

2. 문제 풀이가 종료 될 때까지 방향의 전환 횟수는 2*N - 1번 일어난다.

 현재 방향의 전환 횟수를 iter라고 하고, 좌,하,우,상의 방향을 순서대로 0,1,2,3이라고 하였을 때

(방향의 순서는 문제에서 제시된 대로 정했다.)

 (1) 현재진행방향 = (iter)%4

 (2) 진행방향크기 = (iter)%2 + 1(단, 마지막 진행방향에선 (iter)%2)

이러한 규칙을 찾아 낼 수 있다.

 

3. 위의 규칙에 따라 iter를 1씩 증가시키며 한 방향으로 진행하는 처리를 할 수 있다.

 

4.  3의 과정에서 한 칸씩 옮겨가는 과정을 처리하여 값을 얻어낸다.

 

소스 코드

---

#include <iostream>
#include <vector>

using namespace std;

typedef struct info{
	int x, y, cost;
};

vector<vector<info>> infoV;
pair<int, int> direction[4] = { {0,-1}, {1,0}, {0,1}, {-1,0} };
int map[1000][1000];
int N;

void init() {
	// left, right는 요소의 2번째 인자의 부호를 바꿔주면 되고, up, down은 요소의 1번째 인자의 부호를 전환
	// 알파의 비율 부분은 모든 요소 처리 이후 따로 계산 
	infoV.push_back({ {-1,0,1}, {-1,-1,7}, {-2,-1,2}, {-1,-2,10}, {1,0,1}, {1,-1,7}, {2,-1,2}, {1,-2,10}, {0,-3,5} }); //left
	infoV.push_back({ {0,-1,1}, {1,-1,7}, {1,-2,2}, {2,-1,10}, {0,1,1}, {1,1,7}, {1,2,2}, {2,1,10}, {3,0,5} });  //down
	infoV.push_back({ {-1,0,1}, {-1,1,7}, {-2,1,2}, {-1,2,10}, {1,0,1}, {1,1,7}, {2,1,2}, {1,2,10}, {0,3,5} });   //right
	infoV.push_back({ {0,-1,1}, {-1,-1,7}, {-1,-2,2}, {-2,-1,10}, {0,1,1}, {-1,1,7}, {-1,2,2}, {-2,1,10}, {-3,0,5} }); // up
}

bool inRange(int x, int y) {
	return (0 <= x && x < N && 0 <= y && y < N);
}

int onePoint(int x, int y, int dir) { 
// 한 지점에 대한 처리
	vector<info> spread = infoV[dir];
	int spreadSand = 0; // 지금까지 퍼져나간 모래, 알파지점을 계산하기 위한 값
	int outSand = 0;    // 범위 밖으로 나간 모래 -> 우리가 원하는 값
	int target_x = x + direction[dir].first;  //문제의 y지점의 행
	int target_y = y + direction[dir].second; //문제의 y지점의 열

	for (int i = 0; i < spread.size(); i++) {
		
		int cost = spread[i].cost * 0.01 * map[target_x][target_y];
		int next_x = x + spread[i].x;
		int next_y = y + spread[i].y;
		spreadSand += cost; //알파 지점의 값을 알기위해 퍼져나간 모래를 더함

		if (inRange(next_x, next_y)) //범위 내에 있다면 모래를 더해줌
			map[next_x][next_y] += cost; 
		else    // 범위 내에 없다면 밖으로 나간 모래 값을 더해줌
			outSand += cost;
	}
	
    // 알파 지점 처리
    //알파 지점은 현재 위치에서 진행방향으로 두 칸 떨어짐
	int next_x = x + direction[dir].first * 2; 
	int next_y = y + direction[dir].second * 2; 
    // 지금까지 퍼져나간 모래의 값을 y지점에서 빼준다.
	int cost = map[target_x][target_y] - spreadSand;
	map[target_x][target_y] = 0;

	if (inRange(next_x, next_y))
		map[next_x][next_y] += cost;
	else
		outSand += cost;
	
	return outSand;
}

info oneDirection(int dir, int len, int x, int y) {
//한 진행방향에 대한 처리
	int sum = 0;

	for (int i = 0; i < len; i++) {
		sum += onePoint(x, y, dir);
		x += direction[dir].first;
		y += direction[dir].second;
	}
	return { x,y,sum };
}

int solve() {

	int ans = 0;
	int iter = -1;
	int x = N / 2;
	int y = N / 2;

	while (++iter < N * 2 - 1) { //방향 전환 횟수
		int len = (iter == (N - 1) * 2) ? iter / 2 : iter / 2 + 1; //마지막 전환에선 len의 크기 증가 x
		info result = oneDirection(iter % 4, len, x, y);
		x = result.x;
		y = result.y;
		ans += result.cost;
	}

	return ans;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init();

	cin >> N;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];

	cout << solve();
}

개발 환경 : VS2017

질문, 지적 환영합니다!