코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
개요
2024년 하반기 삼성 코딩테스트 당시 해당 문제를 푸려고 했으나, 생각보다 고려해야 할 조건이 너무 많고 코드가 길어지면서 잔실수도 많이 나와 실수를 잡는데만 시간을 많이 소요했고 4시간 만에 풀이하기엔 부족했던 거 같다. 시험이 종료 후 다시 풀어보려고 한다.
풀이 방법
우선 해당 문제는 시뮬레이션 문제이므로 풀이하는데 필요한 절차를 정리해 보자
// 메두사의 이동
// 전사가 있을 경우 해당 전사가 사라짐
// 상하좌우 위주로
// 메두사의 시선
// 상하좌우 하나의 방향을 선택해 바라본다. (가장 많은 전사를 멈출 수 있는 방향)
// 메두사의 시선에 보인 전사는 한 턴을 쉰다.
// 메두사의 시선에서 앞 전사에 의해 숨을 수 있으면 스턴 상태가 되지 않는다.
// 같은 칸에 두명의 전사면 모두 스턴이 된다.
// 전사들의 이동
// 스턴 상태이면 한 턴을 쉰다.
// 최대 두 칸까지 이동 메두사와 가까워 지는 방향으로
// 벽으로 이동이 가능하며, 메두사의 시선이 있는 곳으로는 가지 못한다.
// 첫 우선순위 상하좌우
// 두번 째 우선순위좌우상하
// 전사의 공격
// 같은 칸에 도달한 전사는 메두사를 공격
// 공격 후 전사는 사라진다.
자료구조선택
우선 메두사와, 전사를 저장하기 위한 자료구조를 선택해야한다.
메두사의 경우 현재위치만 저장하면 되므로 pair<int, int>를 사용했다.
전사의 경우 현재 위치와, 현재의 상태(사라진 상태, 스턴 상태, 활동 상태)를 저장해야 하므로 구조체를 사용했다.
여기서 고민한 점은 메두사의 시선을 통해 전사를 스턴상태로만들기 위해 메두사의 시선에 해당하는 칸에 있는 전사를 찾기 위한 배열을 따로 저장을 해두어야 하나 고민을 했다. 하지만 그냥 메두사의 시선 처리를 한 후 모든 전사를 탐색해서 해당 전사가 시선에 위치하는지 탐색을 해도 시간복잡도가 N^2*M = 1초 미만이므로 모두 탐색하는 방법을 선택했다.
1. 메두사의 이동 경로를 설정하자.
먼저 메두사의 이동 경로를 확정해야한다.
확정하지 않고 매턴마다 메두사의 이동경로를 결정하기엔 전사들의 위치를 모두 저장해야 하기 때문에 문제가 매우 복잡해진다.
그렇기 때문에 문제를 시작하기 전에 메두사의 이동경로를 bfs를 통해 확정을 짓고 매턴마다 정해진 경로를 따라 메두사를 이동시키면 된다.
또한 이렇게 해야 길이 없는 경우가 발생했을 때 빠르게 탐색을 종료할 수 있다.
최단 경로이기 때문에 bfs를 사용했다.
또한 저장된 bfs경로는 메두사 경로의 역이므로 reverse를 통해 뒤집어 주어야 한다.
그러기 위해 parents배열을 두어서 이전 좌표를 저장해 두고 탐색이 종료되면 parents를 통해 -1이 될 때까지 경로를 저장해 준다.
void bfs() {
int dy[4] = {-1, 1, 0, 0}; // 상하좌우 설정
int dx[4] = {0, 0, -1, 1};
pair<int, int> parents[51][51];
queue<pair<int, int> > q;
visited[medusa.first][medusa.second] = 1;
q.push(make_pair(medusa.first, medusa.second));
parents[medusa.first][medusa.second] = make_pair(-1, -1);
while(!q.empty()) {
pair<int, int> now = q.front();
q.pop();
if (now.first == end_p.first && now.second == end_p.second){
break;
}
for (int i = 0;i < 4;i++) {
int ny = now.first + dy[i];
int nx = now.second + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if (visited[ny][nx] == 1) continue;
if (board[ny][nx] == 1) continue;
pair<int, int> next = make_pair(ny, nx);
parents[ny][nx] = make_pair(now.first, now.second);
q.push(next);
visited[ny][nx] = 1;
}
}
if (visited[end_p.first][end_p.second] == 0) { //길이 없는 경우
flag = 1;
return ;
}
pair<int, int> now = make_pair(end_p.first, end_p.second);
while (now.first != -1 && now.second != -1) {
m_path.push_back(make_pair(now.first, now.second));
now = parents[now.first][now.second];
}
reverse(m_path.begin(), m_path.end());
return ;
}
이후 메두사를 이동하고, 전사가 있다면 해당 전사를 state상태를 2로 설정해서 제거처리 했다.
2. 메두사의 시선처리, 전사가 다른 전사를 가려주는 부분 구현
메두사의 시선이 닿는 곳을 처리하기 위해 dfs함수를 사용했다.
메두사의 dfs재귀구조를 통해 트리 모양을 형성할 수 있다.
하지만 전사의 경우 메두사와의 위치 상관관계에 따라 트리의 한쪽만 가려주므로 이에 따라 dfs 함수를 설계하기 위해 파라미터에 type변수를 설정하여, 설계했다.
각각의 상하좌우에 따라 메두사와 전사의 상대적 위치를 고려해서 전사에 의해 가려지는 부분을 구현했다. (see_w 함수)
또한 dfs_dir배열을 선언해 상화좌우로의 시선을 만들 수 있도록 미리 배열을 선언했다.
int dfs_dir[4][3][2] = {{{-1, -1}, {-1, 0}, {-1, 1}}, //상하 좌우 빔
{{1, -1}, {1, 0}, {1, 1}},
{{-1, -1}, {0, -1}, {1, -1}},
{{-1, 1}, {0, 1}, {1, 1}}};
void dfs(pair<int, int> s, int dir, int fill, int type) { // 시작점, 방향, 채워야 할값
int y = s.first, x = s.second;
if (type == 0) {
for (int i = 0;i < 3;i++) {
pair<int, int> nn;
nn.first = y + dfs_dir[dir][i][0];
nn.second = x + dfs_dir[dir][i][1];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) continue;
if (see[nn.first][nn.second] == fill) continue;
see[nn.first][nn.second] = fill;
dfs(nn, dir, fill, type);
}
}
else if (type == 1) { // 0, 1
for (int i = 0;i < 2;i++) {
pair<int, int> nn;
nn.first = y + dfs_dir[dir][i][0];
nn.second = x + dfs_dir[dir][i][1];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) continue;
if (see[nn.first][nn.second] == fill) continue;
see[nn.first][nn.second] = fill;
dfs(nn, dir, fill, type);
}
}
else if (type == 2) { // 1
pair<int, int> nn;
nn.first = y + dfs_dir[dir][1][0];
nn.second = x + dfs_dir[dir][1][1];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) return ;
if (see[nn.first][nn.second] == fill) return;
see[nn.first][nn.second] = fill;
dfs(nn, dir, fill, type);
}
else if (type == 3) { // 1, 2
for (int i = 1;i < 3;i++) {
pair<int, int> nn;
nn.first = y + dfs_dir[dir][i][0];
nn.second = x + dfs_dir[dir][i][1];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) continue;
if (see[nn.first][nn.second] == fill) continue;
see[nn.first][nn.second] = fill;
dfs(nn, dir, fill, type);
}
}
return ;
}
void see_w(pair<int, int> m, int dir) { //
int cnt = 0;
for (int i = 0;i < w.size();i++) {
if (w[i].state == 2) continue;
if (see[w[i].y][w[i].x] == 1) {
if (dir == 0 || dir == 1) {
if (m.second > w[i].x) dfs(make_pair(w[i].y, w[i].x), dir, 0, 1);
else if (m.second == w[i].x) dfs(make_pair(w[i].y, w[i].x), dir, 0, 2);
else dfs(make_pair(w[i].y, w[i].x), dir, 0, 3);
}
else {
if (m.first > w[i].y) dfs(make_pair(w[i].y, w[i].x), dir, 0, 1);
else if (m.first == w[i].y) dfs(make_pair(w[i].y, w[i].x), dir, 0, 2);
else dfs(make_pair(w[i].y, w[i].x), dir, 0, 3);
}
}
}
}
3. 전사의 이동
전사의 이동에서는 자신이 사라진 상태인지 (state == 2)
자신이 스턴 상태인지 (state == 1)
정상 상태인지 (state == 0)에 따라 설정했다.
또한 메두사의 시선에 해당하는 곳은 이동하지 못한다.
메두사와 가까워지는 방향인지 distance 함수를 사용해서 판단했다.
전체 코드
#include <iostream>
#include <vector>
#include <math.h>
#include <memory.h>
#include <queue>
#include <algorithm>
using namespace std;
struct Warrior {
int y;
int x;
int state; //0은 정상 1은 스턴 2는 죽음
Warrior(int y, int x) :y(y), x(x), state(0) {}
};
int see[51][51];
int board[51][51];
vector<pair<int, int> > m_path;
int n, m;
vector<int> ans;
pair<int, int> medusa; // 메두사의 시작
pair<int, int> end_p;
vector<Warrior> w;
int visited[51][51];
int distance(pair<int, int> a, pair<int, int> b) {
return abs(a.first - b.first) + abs(a.second - b.second);
}
void input() {
cin >> n >> m;
cin >> medusa.first >> medusa.second;
cin >> end_p.first >> end_p.second;
int a, b;
for (int i = 0;i < m;i++) {
cin >> a >> b;
w.push_back(Warrior(a, b));
}
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
cin >> board[i][j];
}
}
}
int flag = 0;
void move_m(int idx) {
medusa = m_path[idx];
for (int i = 0;i < w.size();i++) { // 겹치는 전사 있는지 탐색
// 메두사가 전사 사라지게 함
if (w[i].state == 2) continue; //이미 죽은 경우
if (w[i].y == medusa.first && w[i].x == medusa.second) w[i].state = 2; // 겹치면 죽음
}
return ;
}
int dfs_dir[4][3][2] = {{{-1, -1}, {-1, 0}, {-1, 1}}, //상하 좌우 빔
{{1, -1}, {1, 0}, {1, 1}},
{{-1, -1}, {0, -1}, {1, -1}},
{{-1, 1}, {0, 1}, {1, 1}}};
void dfs(pair<int, int> s, int dir, int fill, int type) { // 시작점, 방향, 채워야 할값
int y = s.first, x = s.second;
if (type == 0) {
for (int i = 0;i < 3;i++) {
pair<int, int> nn;
nn.first = y + dfs_dir[dir][i][0];
nn.second = x + dfs_dir[dir][i][1];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) continue;
if (see[nn.first][nn.second] == fill) continue;
see[nn.first][nn.second] = fill;
dfs(nn, dir, fill, type);
}
}
else if (type == 1) { // 0, 1
for (int i = 0;i < 2;i++) {
pair<int, int> nn;
nn.first = y + dfs_dir[dir][i][0];
nn.second = x + dfs_dir[dir][i][1];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) continue;
if (see[nn.first][nn.second] == fill) continue;
see[nn.first][nn.second] = fill;
dfs(nn, dir, fill, type);
}
}
else if (type == 2) { // 1
pair<int, int> nn;
nn.first = y + dfs_dir[dir][1][0];
nn.second = x + dfs_dir[dir][1][1];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) return ;
if (see[nn.first][nn.second] == fill) return;
see[nn.first][nn.second] = fill;
dfs(nn, dir, fill, type);
}
else if (type == 3) { // 1, 2
for (int i = 1;i < 3;i++) {
pair<int, int> nn;
nn.first = y + dfs_dir[dir][i][0];
nn.second = x + dfs_dir[dir][i][1];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) continue;
if (see[nn.first][nn.second] == fill) continue;
see[nn.first][nn.second] = fill;
dfs(nn, dir, fill, type);
}
}
return ;
}
void see_w(pair<int, int> m, int dir) { //
int cnt = 0;
for (int i = 0;i < w.size();i++) {
if (w[i].state == 2) continue;
if (see[w[i].y][w[i].x] == 1) {
if (dir == 0 || dir == 1) {
if (m.second > w[i].x) dfs(make_pair(w[i].y, w[i].x), dir, 0, 1);
else if (m.second == w[i].x) dfs(make_pair(w[i].y, w[i].x), dir, 0, 2);
else dfs(make_pair(w[i].y, w[i].x), dir, 0, 3);
}
else {
if (m.first > w[i].y) dfs(make_pair(w[i].y, w[i].x), dir, 0, 1);
else if (m.first == w[i].y) dfs(make_pair(w[i].y, w[i].x), dir, 0, 2);
else dfs(make_pair(w[i].y, w[i].x), dir, 0, 3);
}
}
}
}
int cnt_stop_w() {
int cnt = 0;
for (int i = 0;i < w.size();i++) {
if (w[i].state == 2) continue; // 죽은 경우는 제외
if (see[w[i].y][w[i].x] == 1) cnt++;
}
return cnt;
}
void see_m() {
int max_cnt = 0, max_dir = 0;
for (int i = 0;i < 4;i++) { // 바라볼 방향 체크
memset(see, 0, sizeof(see));
dfs(medusa, i, 1, 0);
see_w(medusa, i);
int now_cnt = cnt_stop_w();
if (now_cnt > max_cnt) {
max_cnt = now_cnt, max_dir = i;
}
}
// 방향 확정 되고 다시 시선 체크
memset(see, 0, sizeof(see));
dfs(medusa, max_dir, 1, 0);
see_w(medusa, max_dir);
int stone_cnt = 0;
for (int i = 0;i < w.size();i++) {
if (see[w[i].y][w[i].x] == 1) {
if (w[i].state == 2) continue;
stone_cnt++;
w[i].state = 1; // 스턴
}
}
ans.push_back(stone_cnt);
}
pair<int, int> w_next_loc_up_down(pair<int, int> s, pair<int, int> e) { //s에서 e로 갈때 방향
int dy[4] = {-1, 1, 0, 0}; // 상하좌우 설정
int dx[4] = {0, 0, -1, 1};
int now_dis = distance(s, e);
for (int i = 0;i < 4;i++) {
pair<int, int> nn;
nn.first = s.first + dy[i];
nn.second = s.second + dx[i];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) continue;
if (see[nn.first][nn.second] == 1) continue;
if (distance(nn, e) < now_dis) return nn;
}
// 갈곳이 없으면
return make_pair(-1, -1);
}
pair<int, int> w_next_loc_left_right(pair<int, int> s, pair<int, int> e) { //s에서 e로 갈때 방향
int dy[4] = {0, 0, -1, 1}; // 좌우상하 설정
int dx[4] = {-1, 1, 0, 0};
int now_dis = distance(s, e);
for (int i = 0;i < 4;i++) {
pair<int, int> nn;
nn.first = s.first + dy[i];
nn.second = s.second + dx[i];
if (nn.first < 0 || nn.second < 0 || nn.first >= n || nn.second >= n) continue;
if (see[nn.first][nn.second] == 1) continue;
if (distance(nn, e) < now_dis) return nn;
}
// 갈곳이 없으면
return make_pair(-1, -1);
}
void move_w() { // 전사 움직임
int w_move_cnt = 0, attack_cnt = 0;
for (int i = 0;i < w.size();i++) {
if (w[i].state == 2) continue; //죽은 경우 다음 패스
if (w[i].state == 1) { // 스턴인 경우 스턴 제거
w[i].state = 0;
continue;
}
pair<int, int> nn = w_next_loc_up_down(make_pair(w[i].y, w[i].x), medusa);
if (nn.first == -1 && nn.second == -1) continue;
//전사 첫 번째 이동
w[i].y = nn.first, w[i].x = nn.second;
w_move_cnt++;
if (nn.first == medusa.first && nn.second == medusa.second) {
w[i].state = 2;
attack_cnt++;
continue;
}
//전사 두 번째 이동
nn = w_next_loc_left_right(make_pair(w[i].y, w[i].x), medusa);
if (nn.first == -1 && nn.second == -1) continue;
//전사 두 번째 이동
w[i].y = nn.first, w[i].x = nn.second;
w_move_cnt++;
if (nn.first == medusa.first && nn.second == medusa.second) {
w[i].state = 2;
attack_cnt++;
continue;
}
}
ans.push_back(w_move_cnt);
ans.push_back(attack_cnt);
}
void bfs() {
int dy[4] = {-1, 1, 0, 0}; // 상하좌우 설정
int dx[4] = {0, 0, -1, 1};
pair<int, int> parents[51][51];
queue<pair<int, int> > q;
visited[medusa.first][medusa.second] = 1;
q.push(make_pair(medusa.first, medusa.second));
parents[medusa.first][medusa.second] = make_pair(-1, -1);
while(!q.empty()) {
pair<int, int> now = q.front();
q.pop();
if (now.first == end_p.first && now.second == end_p.second){
break;
}
for (int i = 0;i < 4;i++) {
int ny = now.first + dy[i];
int nx = now.second + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if (visited[ny][nx] == 1) continue;
if (board[ny][nx] == 1) continue;
pair<int, int> next = make_pair(ny, nx);
parents[ny][nx] = make_pair(now.first, now.second);
q.push(next);
visited[ny][nx] = 1;
}
}
if (visited[end_p.first][end_p.second] == 0) { //길이 없는 경우
flag = 1;
return ;
}
pair<int, int> now = make_pair(end_p.first, end_p.second);
while (now.first != -1 && now.second != -1) {
m_path.push_back(make_pair(now.first, now.second));
now = parents[now.first][now.second];
}
reverse(m_path.begin(), m_path.end());
return ;
}
void sol() {
bfs(); // 메두사의 경로를 설정함
if (flag == 1) {
return ;
}
for (int i = 1;i < m_path.size()-1;i++) { // 메두사 이동하기
move_m(i);
see_m();
move_w();
}
}
int main() {
// 여기에 코드를 작성해주세요.
ios::sync_with_stdio(false);
cin.tie(0);
memset(visited, 0, sizeof(visited));
input();
sol();
if (flag == 1) {
cout << -1;
return 0;
}
for (int i = 0;i < ans.size();i = i + 3) {
cout << ans[i + 1] << " " << ans[i] << " " << ans[i+2] << "\n";
}
cout << 0;
return 0;
}
'Algorithm' 카테고리의 다른 글
| [프로그래머스] 미로 탈출 명령어 (c++) (1) | 2024.12.31 |
|---|---|
| [프로그래머스] 도넛과 막대 그래프 (c++) 엣지 케이스 (0) | 2024.12.29 |
| [프로그래머스] 수레 움직이기 C++ (0) | 2024.12.24 |
| [백준] 히스토그램에서 가장 큰 직사각형 (c++) 분할 정복 (0) | 2024.12.24 |
| [백준] 텀 프로젝트 (c++) dfs (0) | 2024.12.24 |