Code Tree | Learning to Code with Confidence
A super-comprehensive, meticulously arranged Coding Learning Curriculum engineered by Algorithm Experts composed of former International Olympiad in Informatics (IOI) medalists.
www.codetree.ai
알고리즘 유형 : 구현, 시뮬레이션, BFS
풀이 시간 : 3시간 12분
문제 풀이
--문제 설명의 경우 생략하겠습니다--
해당 문제는 총 4가지 동작의 반복으로 나눌 수 있다.
1. 메두사 이동
2. 메두사의 최적의 시야각 찾기
3. 전사들의 이동
4. 각 라운드별 결과 출력
1. 메두사 이동
메두사는 출발 위치에서 공원까지 최단 경로를 따른다. 또한, 메두사는 전사들과 달리 도로 위에서만 이동을 할 수 있으며, 상 - 하 - 좌 - 우 의 우선순위를 갖는다.
이동에 관련하여 동적으로 변하는 전사들의 위치는 신경쓸 필요가 없고, 최단 경로만 찾으면 되기 때문에 각 라운드마다 최단 경로를 찾는 대신, 본게임이 시작하기 직전에 최단 경로를 먼저 찾아주고 간다면 실행시간의 효율을 높일 수 있을 것이다.
경로 찾기 알고리즘은 간단하다.
BFS를 활용해 출발지부터 목적지까지 최단 경로를 찾는 과정 중 새로운 정점에 이전 정점 정보를 함께 저장해주기만 하면 된다.
도착지까지 이동이 완료되었다면, 도착지부터 다시 출발지까지 이전 정점 정보를 탐색해가며 2차원 grid에 정보를 저장해나가면 된다.
모든 과정을 수행하면 현재 정점에서 다음 정점의 정보를 저장하고 있는 path 그리드를 얻을 수 있다.
int find_path(int sr, int sc) {
queue<pair<int, int>> q;
q.push({ sr, sc });
int visited[51][51] = { 0, };
visited[sr][sc] = 1;
pair<int, int> tmp_path[51][51]; // 이전에 왔던 경로를 저장
int arrival = 0;
while (!q.empty()) {
int r = q.front().first, c = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (isValid(nr, nc) && !visited[nr][nc] && !medusa_grid[nr][nc]) {
tmp_path[nr][nc] = { r, c };
if (nr == end_r && nc == end_c) {
arrival = 1;
break;
}
q.push({ nr, nc });
visited[nr][nc] = 1;
}
}
if (arrival)
break;
}
if (!arrival)
return 1;
// 경로 생성
int br, bc;
int nr = end_r, nc = end_c;
while (1) {
br = tmp_path[nr][nc].first, bc = tmp_path[nr][nc].second;
path[br][bc] = { nr, nc };
nr = br;
nc = bc;
if (nr == medusa_r && nc == medusa_c)
break;
}
return 0;
}
2. 메두사의 최적의 시야각 찾기
이 과정을 해결하는 것이 아마 해당 문제의 키포인트지 않을까 싶다.
메두사의 시선을 선택하는 다음과 같은 조건이 붙는다.
1. 최대한 전사를 많이 볼 수 있는 방향을 바라본다.
2. 방향이 여러개라면, 상하좌우의 우선순위로 결정한다.
해당 문제를 풀기 위해 메두사의 시야각과 다른 전사에 가려지는 영역을 각각 구해주었다.
먼저 방향 벡터를 2차원으로 설정해주어 다이아몬드 방향으로 퍼져나가도록 설정하였다.
int msr[4][3] = { {-1, -1, -1}, {1, 1, 1}, {-1, 0, 1}, {-1, 0, 1} };
int msc[4][3] = { {-1, 0, 1}, {-1, 0, 1}, {-1, -1, -1}, {1, 1, 1} };이렇게 설정한 뒤, 방향 별로 시야각 정점을 탐색해 나간다면 불필요한 중복 탐색이 발생할 수 있기 때문에 최적화가 필요해 보이지만, 일단 진행해보았다.
이후, 전사가 퍼져나가는 시야에 최초로 들어오게 된다면, 전사 count를 진행해준 뒤, 해당 전사에 의해 발생하는 그림자 영역을 바로 찾아주었다.
그림자 영역의 경우, 메두사와 동일 선상에 있는 경우와, 대각선 방향에 존재하는 경우를 구분해주어야 한다.
1. 그림자 영역의 경우에는, 해당 용사 이후 부분만 가려주면 된다.
2. 대각선 영역의 경우, 다이아몬드 꼴로 가려지지 않는 부분이 존재한다.
따라서 그림자 영역을 생성해줄 때, 해당 영역에 좌표가 위치하는지를 판단하여 탐색 여부를 결정해준다면 그림자를 생성해줄 수 있다.
해당 영역을 탐색하기 위해서 (전사의 위치, 메두사의 위치, 현재 좌표, 메두사의 시야각) 이 네 정보를 활용하여 판단을 진행해주었다.
// 동일 선상일 경우
if (nr == medusa_r || nc == medusa_c) {
nsr = safe_r + msr[d][1], nsc = safe_c + msc[d][1];
if (isValid(nsr, nsc) && !tmp_safe_zone[nsr][nsc]) {
safe_queue.push({ nsr, nsc });
tmp_safe_zone[nsr][nsc] = 1;
}
}
else {
// 방향별로 나눠서 가능 여부 판단하기
for (int sd = 0; sd < 3; sd++) {
nsr = safe_r + msr[d][sd], nsc = safe_c + msc[d][sd];
if (isValid(nsr, nsc) && checkSight(d, nr, nc, nsr, nsc) && !tmp_safe_zone[nsr][nsc]) {
safe_queue.push({ nsr, nsc });
tmp_safe_zone[nsr][nsc] = 1;
}
}
}해당 코드는 그림자( safe_zone )의 탐색 여부를 타나내었고,
bool checkSight(int d, int wr, int wc, int r, int c) {
switch (d) {
// 상
case 0:
if ((wc < c && c <= medusa_c) || (c < wc && c >= medusa_c))
return false;
return true;
// 하
case 1:
if ((wc < c && c <= medusa_c) || (c < wc && c >= medusa_c))
return false;
return true;
// 좌
case 2:
if ((r > wr && r <= medusa_r) || (r < wr && r >= medusa_r))
return false;
return true;
// 우
case 3:
if ((r > wr && r <= medusa_r) || (r < wr && r >= medusa_r))
return false;
return true;
}
}해당 코드는 경계에 걸치는 영역인지를 판단하기 위해 사용하였다.
3. 전사들의 이동
전사들은 총 2번 이동할 수 있다. 따라서, 같은 과정을 2번 반복해주어야 한다.
또한, 첫번째 이동과 두번째 이동 간 이동우선순위가 다르기 때문에, 이를 잘 고려해서 풀어주어야 한다.
해당 이동은 간단하게 시뮬레이션을 통해서 풀어나갈 수 있었다.
전사 정보는 구조체를 활용한 list를 생성해주었다. 구조체의 경우 (전사 r, 전사 c, 스턴 여부, 사망 여부) 정보를 담고 있다.
먼저, 메두사에 의해 죽은 전사의 경우 즉시 continue를 진행해주었고, 시야각에 들어와 스턴에 걸린 전사들은 스턴을 풀어준 뒤, continue해주었다.
이후, 모든 전사들은 총 2번 이동하게 되는데, 현재 메두사와의 거리보다 길어지는 방향으로는 이동할 수 없다.
이 말은 즉슨, 현재 자리에서 이동하지 않을 수도 있다는 의미이다. 따라서 이동할 때마다 해당 경우들을 판단해주어야 한다.
1. 전사가 이동하였는가 ?
2. 전사가 메두사를 잡았는가 ?
모든 시뮬레이션이 끝난 뒤, 전사의 구조체에 마지막 위치를 업데이트해주고, warrior_grid에 전사를 업데이트해주면 된다.
4. 각 라운드별 결과 출력
해당 과정이 모두 끝난 뒤, return받은 결과들을 출력해주면 된다. 게임이 끝나게 되는 경우를 확인하는 과정은 1번. 메두사의 이동 과정에서 확인하면 된다.
코드
/*
n x n
도로 : 0, 도로가 아닌 곳 : 1
메두사는 오직 도로만을 따라 최단 경로로 공원까지 이동함
M명의 전사들은 메두사를 향해 최단경로로 이동함. 어느 칸이든지 이동 가능함(맨해튼거리 써서 가장 가까운 곳으로 이동 가능)
[메두사]
도로를 따라 한 칸 이동, 최단경로를 따른다.
메두사가 이동한 칸에 전사가 있을 경우, 전사는 사라진다.
여러 최단경로가 가능하다면, 상하좌우의 우선순위를 따른다.
집으로부터 공원까지 경로가 없을 수도 있음
[메두사의 시선]
상하좌우 하나의 방향을 선택해 바라본다.
바라보는 방향으로 90도의 시야각을 가지며, 시야각 범위 전사를 볼 수 있음
다른 전사에 가려진 전사의 경우, 보이지 않음
전사가 동일한 방향으로 바라본 범위에 포함된 모든 칸은 메두사하넽 보이지 않음(그림 참조)
메두사가 본 전사들은 모두 돌로 변해 현재 턴에는 움직일 수 없음
해당 칸 전사들 모두 돌로 변함
메두사는 전사를 가장 많이 볼 수 있는 방향을 바라봄
상하좌우 우선순위
[전사 이동]
최대 두 칸까지 이동
이동중 칸 공유 가능
메두사의 시야에 들어오는 곳으로는 이동 불가능
1. 상하좌우 우선순위로 거리를 줄일 수 있음
2. 좌우상하 우선순위로 한 번 더 이동
[전사 공격]
전사는 메두사를 공격하고 사라진다.
모든 전사가 이동한 거리의 합 , 돌이 된 전사의 수, 공격한 전사의 수 출력
메두사가 도착하면 0 출력 후 끝
풀이 :
메두사 이동 : BFS로 사전에 경로를 찾아둔다.
메두사 시야 : 2개의 2차원 배열을 사용. sight, safe_zone
sight가 0이거나 sight면서 safe_zone이 1인 경우에만 생존
sight : 상하좌우로 메두사 시야를 방향벡터 제공 -> bfs로 맵 생성하기
safe_zone : sight 중 사람을 만나면 재귀 bfs 들어가기
전사 이동 : 맨해튼거리로 계산
전사의 위치는 구조체로 생성해두기
전사 정보 : 위치, 스턴, 죽은 경우
*/
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct warrior {
int r, c, stun, dead;
};
int n, m;
int medusa_r, medusa_c, end_r, end_c;
int medusa_grid[51][51];
pair<int, int> path[51][51];
int warrior_grid[51][51];
warrior warrior_list[301];
int sight[51][51];
int safe_zone[51][51];
int dr[4] = { -1, 1, 0, 0 };
int dc[4] = { 0, 0, -1, 1 };
int msr[4][3] = { {-1, -1, -1}, {1, 1, 1}, {-1, 0, 1}, {-1, 0, 1} };
int msc[4][3] = { {-1, 0, 1}, {-1, 0, 1}, {-1, -1, -1}, {1, 1, 1} };
bool isValid(int r, int c) {
return 0 <= r && r < n && 0 <= c && c < n;
}
bool checkSight(int d, int wr, int wc, int r, int c) {
switch (d) {
// 상
case 0:
if ((wc < c && c <= medusa_c) || (c < wc && c >= medusa_c))
return false;
return true;
// 하
case 1:
if ((wc < c && c <= medusa_c) || (c < wc && c >= medusa_c))
return false;
return true;
// 좌
case 2:
if ((r > wr && r <= medusa_r) || (r < wr && r >= medusa_r))
return false;
return true;
// 우
case 3:
if ((r > wr && r <= medusa_r) || (r < wr && r >= medusa_r))
return false;
return true;
}
}
int get_distance(int r1, int c1, int r2, int c2) {
return abs(r1 - r2) + abs(c1 - c2);
}
int find_path(int sr, int sc) {
queue<pair<int, int>> q;
q.push({ sr, sc });
int visited[51][51] = { 0, };
visited[sr][sc] = 1;
pair<int, int> tmp_path[51][51]; // 이전에 왔던 경로를 저장
int arrival = 0;
while (!q.empty()) {
int r = q.front().first, c = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (isValid(nr, nc) && !visited[nr][nc] && !medusa_grid[nr][nc]) {
tmp_path[nr][nc] = { r, c };
if (nr == end_r && nc == end_c) {
arrival = 1;
break;
}
q.push({ nr, nc });
visited[nr][nc] = 1;
}
}
if (arrival)
break;
}
if (!arrival)
return 1;
// 경로 생성
int br, bc;
int nr = end_r, nc = end_c;
while (1) {
br = tmp_path[nr][nc].first, bc = tmp_path[nr][nc].second;
path[br][bc] = { nr, nc };
nr = br;
nc = bc;
if (nr == medusa_r && nc == medusa_c)
break;
}
return 0;
}
int init() {
cin >> n >> m;
cin >> medusa_r >> medusa_c >> end_r >> end_c;
for (int i = 0; i < m; i++) {
cin >> warrior_list[i].r >> warrior_list[i].c;
warrior_grid[warrior_list[i].r][warrior_list[i].c]++;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> medusa_grid[i][j];
}
}
// 0. 메두사 길 찾기
if (find_path(medusa_r, medusa_c))
return 0;
return 1;
}
int get_sight() {
// 준비물 : tmp sight 그리드, tmp safe zone 그리드 기절시킨 용사 수
int tmp_sight[51][51];
int tmp_safe_zone[51][51];
int warrior_cnt = 0;
for (int d = 0; d < 4; d++) {
int tmp_warrior_cnt = 0;
memset(tmp_sight, 0, sizeof(tmp_sight));
memset(tmp_safe_zone, 0, sizeof(tmp_safe_zone));
queue<pair<int, int>> q;
q.push({ medusa_r, medusa_c });
while (!q.empty()) {
int r = q.front().first, c = q.front().second;
q.pop();
for (int nd = 0; nd < 3; nd++) {
int nr = r + msr[d][nd], nc = c + msc[d][nd];
if (isValid(nr, nc) && !tmp_sight[nr][nc] && !tmp_safe_zone[nr][nc]) {
// 첫 워리어를 발견한 경우
if (warrior_grid[nr][nc]) {
tmp_warrior_cnt += warrior_grid[nr][nc];
// 새로운 tmp_safe_zone 생성
queue<pair<int, int>> safe_queue;
safe_queue.push({ nr, nc });
int safe_r, safe_c, nsr, nsc;
while (!safe_queue.empty()) {
safe_r = safe_queue.front().first, safe_c = safe_queue.front().second;
safe_queue.pop();
// 동일 선상일 경우
if (nr == medusa_r || nc == medusa_c) {
nsr = safe_r + msr[d][1], nsc = safe_c + msc[d][1];
if (isValid(nsr, nsc) && !tmp_safe_zone[nsr][nsc]) {
safe_queue.push({ nsr, nsc });
tmp_safe_zone[nsr][nsc] = 1;
}
}
else {
// 방향별로 나눠서 가능 여부 판단하기
for (int sd = 0; sd < 3; sd++) {
nsr = safe_r + msr[d][sd], nsc = safe_c + msc[d][sd];
if (isValid(nsr, nsc) && checkSight(d, nr, nc, nsr, nsc) && !tmp_safe_zone[nsr][nsc]) {
safe_queue.push({ nsr, nsc });
tmp_safe_zone[nsr][nsc] = 1;
}
}
}
}
}
q.push({ nr, nc });
tmp_sight[nr][nc] = 1;
}
}
}
// 모든 경우 완료하고 업데이트만을 기다리는 상황
if (warrior_cnt < tmp_warrior_cnt) {
// 맵 업데이트
warrior_cnt = tmp_warrior_cnt;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sight[i][j] = tmp_sight[i][j];
safe_zone[i][j] = tmp_safe_zone[i][j];
}
}
}
}
// 돌로 변한 전사 찾기(맵에서 사라지는건 아님)
int stone_man = 0;
for (int i = 0; i < m; i++) {
if (warrior_list[i].dead)
continue;
int r = warrior_list[i].r, c = warrior_list[i].c;
if (sight[r][c] && !safe_zone[r][c]) {
stone_man++;
warrior_list[i].stun = 1;
}
}
return stone_man;
}
pair<int, int> warrior_move() {
int r, c, nr, nc, dist, new_dist, flag;
int gr = -1, gc = -1;
int braveman = 0, move = 0;
for (int w = 0; w < m; w++) {
// 죽은 애 continue
if (warrior_list[w].dead)
continue;
// 스턴인 애는 풀어주고 continue
if (warrior_list[w].stun) {
warrior_list[w].stun = 0;
continue;
}
// 나머지는 두 번 씩 이동하기
r = warrior_list[w].r, c = warrior_list[w].c;
dist = get_distance(r, c, medusa_r, medusa_c);
new_dist = 2500;
flag = 0;
// 첫 번째 이동
for (int d = 0; d < 4; d++) {
nr = r + dr[d], nc = c + dc[d];
if (isValid(nr, nc) && (!sight[nr][nc] || safe_zone[nr][nc])) {
new_dist = get_distance(nr, nc, medusa_r, medusa_c);
if (new_dist < dist) {
gr = nr;
gc = nc;
dist = new_dist;
flag = 1;
}
}
}
// 못움직인 경우, continue
if (!flag) {
continue;
}
move++;
// 메두사를 1트만에 잡은 경우 업데이트
if (gr == medusa_r && gc == medusa_c) {
warrior_list[w].dead = 1;
braveman++;
warrior_grid[warrior_list[w].r][warrior_list[w].c]--; // 이전 위치 지워주기
continue;
}
r = gr, c = gc;
flag = 0;
// 두번째 이동
for (int d = 0; d < 4; d++) {
nr = r + dr[(d + 4 + 2) % 4], nc = c + dc[(d + 4 + 2) % 4];
if (isValid(nr, nc) && (!sight[nr][nc] || safe_zone[nr][nc])) {
new_dist = get_distance(nr, nc, medusa_r, medusa_c);
if (new_dist < dist) {
gr = nr;
gc = nc;
dist = new_dist;
flag = 1;
}
}
}
// 못움직인 경우, continue
if (!flag) {
warrior_grid[warrior_list[w].r][warrior_list[w].c]--; // 이전 위치 지워주기
warrior_list[w].r = r, warrior_list[w].c = c;
warrior_grid[r][c]++;
continue;
}
move++;
// 메두사를 2트만에 잡은 경우 업데이트
if (gr == medusa_r && gc == medusa_c) {
warrior_list[w].dead = 1;
braveman++;
warrior_grid[warrior_list[w].r][warrior_list[w].c]--; // 이전 위치 지워주기
continue;
}
// 모두 움직인 경우
warrior_grid[warrior_list[w].r][warrior_list[w].c]--; // 이전 위치 지워주기
warrior_list[w].r = gr, warrior_list[w].c = gc;
warrior_grid[gr][gc]++;
}
return { move, braveman };
}
void simulation() {
int next_r, next_c;
int total_move, stone_man, real_warriors;
while (1) {
// 0. 변수 초기화
total_move = 0, stone_man = 0, real_warriors = 0;
// 1. 메두사 이동
int next_r = path[medusa_r][medusa_c].first, next_c = path[medusa_r][medusa_c].second;
medusa_r = next_r, medusa_c = next_c;
// 1-2. 메두사 도착 여부 확인
if (medusa_r == end_r && medusa_c == end_c) {
cout << 0 << '\n';
break;
}
// 1-3. 사라지는 전사 찾기
for (int i = 0; i < m; i++) {
if (warrior_list[i].r == medusa_r && warrior_list[i].c == medusa_c)
warrior_list[i].dead = 1;
}
warrior_grid[medusa_r][medusa_c] = 0;
// 2. 메두사 바라보기
stone_man = get_sight();
// 3. 용사 이동
pair<int, int> val = warrior_move();
total_move = val.first, real_warriors = val.second;
// 4. 결과 출력
cout << total_move << ' ' << stone_man << ' ' << real_warriors << '\n';
}
}
int main() {
int game_start = init();
if (!game_start) {
cout << -1 << '\n';
}
else {
simulation();
}
}배운 점
아이디어를 구상하고 함수화를 진행하지 않아서 그런가 코드가 생각보다 복잡하고 어지럽게 작성되었다. 클린 코드 작성을 위해 항상 힘써야 할 것 같다.
또한, BFS 탐색 과정에서 중복된 정점 탐색이 반복되고 있는데, 이를 해결하지 못했다. 또한, 전사의 이동 부분에서도 최적화를 진행할 수 있었던 것 같은데 복잡하게 코드를 작성하여 본인이 헷갈렸던 것 같다.
이후 문제를 다시 한 번 풀어보며 해당 부분을 개선해나갈 수 있도록 노력해야겠다.
'PS > CodeTree' 카테고리의 다른 글
| [ 코드트리 ] 미지의 공간 탈출 (Python) (0) | 2024.10.29 |
|---|