🔗 문제
https://www.acmicpc.net/problem/23031
밤이 되면 어두워지는 다솔관에는 좀비가 나온다는 괴담이 있다. 그 좀비들의 정체는 바로 시험 기간에 공부하느라 지친 학생들이었다. 지친 학생들은 멀리서 보면 흡사 좀비이므로 학생 좀비라고 부르자. 아리는 낮에 공부하다가 깜빡하고 책을 두고 와서 밤에 다시 다솔관 4층으로 가야 한다. 밤에 다솔관 4층에 도착한 아리는 겁이 많아서 학생 좀비들을 마주친다면 기절해버리고 말 것이다. 아리는 기절 하지 않고 무사히 책을 찾아 돌아가고 싶다.
N × N으로 이루어진 다솔관 4층 곳곳에는 형광등 스위치와 학생 좀비들이 있다. 아리는 가장 왼쪽 위인 (1, 1)에서 출발하고 아리와 학생 좀비들은 모두 아래 방향을 보고 있다. 아리는 주어진 순서 A에 따라 이동을 한다. 문자열 A는 F, L, R로 구성되어 있으며, F는 앞으로 1칸 전진, L은 아리가 현재 바라보고 있는 방향을 기준으로 왼쪽으로 90도 방향 전환, R은 오른쪽으로 90도 방향을 전환한다. 다솔관 4층 주변에는 벽이 있어서 N × N 밖으로는 이동할 수 없다. 벽에 부딪히게 되면 전진하지 못하고 제자리에 머문다.
밤에는 학생들이 별로 없어서, 다솔관 4층은 암전 상태이다. 겁이 많은 아리는 형광등 스위치가 있는 칸에 도착하면 그 곳에 학생 좀비가 있더라도 학생 좀비랑 마주치기 전에 스위치를 켠다. 스위치를 켜게 되면 해당 스위치가 있는 칸과 상, 하, 좌, 우, 대각선 네 방향으로 1칸씩 불을 밝힌다. 스위치는 한 번 켜게 되면 꺼지지 않는다. 아리가 이동을 마칠 때마다 학생 좀비들은 자신이 보고 있는 방향으로 한 칸 전진한다. 만약 학생 좀비들이 벽에 부딪히게 되면 제자리에서 뒤를 돌아 반대 방향을 바라본다.
아리는 불이 꺼져있는 칸에서 학생 좀비와 함께 있으면 괴담에서 나오는 좀비로 착각하여 그 자리에서 바로 기절해 다음 날 아침에 깨어난다. 하지만 불이 켜져 있는 칸이거나 스위치가 있는 칸에서는 평범한 학생인 것을 알아보고 기절하지 않는다.
✏️ 풀이
구현 문제는 조건을 지키기만 하면 빨리 풀 수 있기 때문에 조건 정리 부터 해야 한다.
while(A의 크기 만큼)
{
// A 확인()
// - F 이동 -> 스위치 확인()
// - L, R 회전
// 좀비의 이동()
}
크게 어떤 흐름이 필요한지 파악한 후, 글을 다시 읽으면서 세세한 조건을 코드로 구현해주기만 하면 된다.
아리 그리고 좀비는 x, y 위치 그리고 d 방향을 가지기 때문에 이 3가지 정보를 관리할 구조체를 생성해주었다.
struct Node
{
int x, y, d;
};
그 후는 딱히 어려운 구현이 없다.
1. A 확인
문자열 A는 F, L, R로 구성되어 있으며,
F는 앞으로 1칸 전진,
L은 아리가 현재 바라보고 있는 방향을 기준으로 왼쪽으로 90도 방향 전환,
R은 오른쪽으로 90도 방향을 전환한다.
벽에 부딪히게 되면 전진하지 못하고 제자리에 머문다.
구현은 글을 잘 읽어야 된다고 말하는 이유
나는 L, R도 이동인 줄 알고 이동시켰다가 틀렸습니다를 봤다 😓
2. 형광등 켜기
아리는 형광등 스위치가 있는 칸에 도착하면 그 곳에 학생 좀비가 있더라도 학생 좀비랑 마주치기 전에 스위치를 켠다.
스위치를 켜게 되면 해당 스위치가 있는 칸과 상, 하, 좌, 우, 대각선 네 방향으로 1칸씩 불을 밝힌다.
스위치는 한 번 켜게 되면 꺼지지 않는다.
3. 좀비 이동
아리가 이동을 마칠 때마다 학생 좀비들은 자신이 보고 있는 방향으로 한 칸 전진한다.
만약 학생 좀비들이 벽에 부딪히게 되면 제자리에서 뒤를 돌아 반대 방향을 바라본다. // 이동이 아니라 회전만
아리가 이동한 후나 좀비가 이동한 후에 마주치는지 확인을 해야 한다.
아리의 이동 직후가 아닌 어차피 좀비 이동할텐데 그냥 좀비 이동 전, 후에 확인하도록 구현했다.
💾 소스
#include <iostream>
#include <string>
#include <vector>
#define MAX_N 15 + 1
#define MAX_D 8
const int dx[MAX_D] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[MAX_D] = {-1, 0, 1, 1, 1, 0, -1, -1};
int N;
std::string A;
char grid[MAX_N][MAX_N];
bool isOn[MAX_N][MAX_N] = {false, };
bool isValid(const int x, const int y)
{
if(x<0 || y<0 || x>=N || y>=N)
return false;
return true;
}
struct Node
{
int x, y, d;
};
std::vector<Node> zombies;
bool getAnswer()
{
Node ari = {0, 0, 5};
for(int t=0; t<A.size(); ++t)
{
if(A[t] == 'F')
{
int x = ari.x + dx[ari.d];
int y = ari.y + dy[ari.d];
// 벽에 부딪히지 않았을 때만 이동함
if(isValid(x, y))
{
ari.x = x; ari.y = y;
// 좀비 있는 칸인지 신경 쓸 필요 없음 그냥 불 켜
if (grid[x][y] == 'S')
{
isOn[x][y] = true;
for (int d=0; d<MAX_D; ++d)
{
int tx = x + dx[d];
int ty = y + dy[d];
if (!isValid(tx, ty)) continue;
isOn[tx][ty] = true;
}
}
}
}
else if (A[t] == 'L') ari.d = (ari.d-2 + MAX_D) % MAX_D;
else if (A[t] == 'R') ari.d = (ari.d+2) % MAX_D;
//std::cout << "[ari] " << ari.x << "\\t" << ari.y << std::endl;
for(int i=0; i<zombies.size(); ++i)
{
if(zombies[i].x == ari.x && zombies[i].y == ari.y && !isOn[ari.x][ari.y])
return false;
int zd = zombies[i].d;
int zdx = zombies[i].x + dx[zd];
int zdy = zombies[i].y + dy[zd];
// 벽에 부딪힌다면 방향만 바꿔
if(!isValid(zdx, zdy))
zombies[i].d = (zombies[i].d + 4) % MAX_D;
else
{
zombies[i].x += dx[zd];
zombies[i].y += dy[zd];
if(zombies[i].x == ari.x && zombies[i].y == ari.y && !isOn[ari.x][ari.y])
return false;
}
//std::cout << "[zombie] " << zombies[i].x << "\\t" << zombies[i].y << "\\t" << zombies[i].d << std::endl;
}
}
return true;
}
int main()
{
std::cin >> N >> A;
for(int i=0; i<N; ++i)
{
for(int j=0; j<N; ++j)
{
std::cin >> grid[i][j];
if(grid[i][j] == 'Z')
{
grid[i][j] = 'O';
zombies.push_back({i, j, 5});
}
else if(grid[i][j] == 'S')
isOn[i][j] = true;
}
}
std::cout << (getAnswer()? "Phew..." : "Aaaaaah!");
return 0;
}