문제
밤이 되면 어두워지는 다솔관에는 좀비가 나온다는 괴담이 있다. 그 좀비들의 정체는 바로 시험 기간에 공부하느라 지친 학생들이었다. 지친 학생들은 멀리서 보면 흡사 좀비이므로 학생 좀비라고 부르자. 아리는 낮에 공부하다가 깜빡하고 책을 두고 와서 밤에 다시 다솔관 4층으로 가야 한다. 밤에 다솔관 4층에 도착한 아리는 겁이 많아서 학생 좀비들을 마주친다면 기절해버리고 말 것이다. 아리는 기절 하지 않고 무사히 책을 찾아 돌아가고 싶다.
N × N으로 이루어진 다솔관 4층 곳곳에는 형광등 스위치와 학생 좀비들이 있다. 아리는 가장 왼쪽 위인 (1, 1)에서 출발하고 아리와 학생 좀비들은 모두 아래 방향을 보고 있다. 아리는 주어진 순서 A에 따라 이동을 한다. 문자열 A는 F, L, R로 구성되어 있으며, F는 앞으로 1칸 전진, L은 아리가 현재 바라보고 있는 방향을 기준으로 왼쪽으로 90도 방향 전환, R은 오른쪽으로 90도 방향을 전환한다. 다솔관 4층 주변에는 벽이 있어서 N × N 밖으로는 이동할 수 없다. 벽에 부딪히게 되면 전진하지 못하고 제자리에 머문다.
밤에는 학생들이 별로 없어서, 다솔관 4층은 암전 상태이다. 겁이 많은 아리는 형광등 스위치가 있는 칸에 도착하면 그 곳에 학생 좀비가 있더라도 학생 좀비랑 마주치기 전에 스위치를 켠다. 스위치를 켜게 되면 해당 스위치가 있는 칸과 상, 하, 좌, 우, 대각선 네 방향으로 1칸씩 불을 밝힌다. 스위치는 한 번 켜게 되면 꺼지지 않는다. 아리가 이동을 마칠 때마다 학생 좀비들은 자신이 보고 있는 방향으로 한 칸 전진한다. 만약 학생 좀비들이 벽에 부딪히게 되면 제자리에서 뒤를 돌아 반대 방향을 바라본다.
아리는 불이 꺼져있는 칸에서 학생 좀비와 함께 있으면 괴담에서 나오는 좀비로 착각하여 그 자리에서 바로 기절해 다음 날 아침에 깨어난다. 하지만 불이 켜져 있는 칸이거나 스위치가 있는 칸에서는 평범한 학생인 것을 알아보고 기절하지 않는다.
아리는 어두워진 다솔관에서 사물함을 찾아 이동하는 중이다. 이동 중에 기절하지 않을 수 있는지 구하여라.
입력
첫째 줄에 한 개의 정수 N(10 ≤ N ≤ 15)이 주어진다.
다음 줄에는 아리가 이동할 순서 문자열 A(10 ≤ A의 길이 ≤ 50)가 주어진다.
다음 줄부터 N × N의 다솔관 지도가 주어진다. 'Z'는 학생 좀비(0 ≤ 학생 좀비의 수 ≤ N × 2)를 나타내고 'S'는 형광등 스위치(0 ≤ 형광등 스위치의 수 ≤ N × 2)를 나타낸다. 'O'는 아무것도 없는 빈칸이다. 아리가 처음에 위치한 (1, 1)은 항상 빈칸인 경우만 입력으로 주어진다.
출력
아리가 기절을 하게 된다면 "Aaaaaah!"를 출력하고, 기절을 하지 않는다면 "Phew..."를 출력하시오.
https://www.acmicpc.net/problem/23031
풀이
핵심 Point
1. 아리가 이동후 좀비와 만나면 기절
2. 이후 좀비가 이동한뒤 아리와 만나면 기절
3. 좀비가 이동하는동안, 주변 다른좀비 데이터와 덮어씌어지면 안된다.
사용된 변수들은 아래와같다.
- map : 좀비 위치(아래 -2 위-3)
- button : 형광등 스위치 위치
- light : 형광등이 밝혀진 구간들 위치들.
- moveMap : 좀비가 이동할시 이동할 위치를 잠시 기록하는 버퍼역할
여기서 moveMap 이 핵심포인트 3번에대한 조치사항이다.
그동안은 map을 모두탐색하며, 좀비를 발견(2, 3)시, 다른값(4, 5)으로 이동할 다음위치에 기록하여 반복했는데,
이 과정에서 이동할 다음위치에 좀비(2, 3)가 있었다면 지워지는 오류가 발생한다!!
따라서, moveMap에 이동할 다음위치에 기록한뒤, map에 다시 복사하는 방법으로 수정했다.
- 입력받고, 메모리 할당하는 부분
- playGame : 명령어갯수만큼 이동(아리, 좀비)하는 부분
이는 방향을 나타내는 변수로 view_dir로 지정한뒤
명령어를 수행한다.
- action : 스위치를 키고, 아리가 좀비와만나는지, 좀비가 이동하는등을 결정하는 부분
3-1. 아리가 스위치를 키는 부분
3-2. 아리가 이동한뒤 좀비랑 만났는지 확인하는 부분
3-3. 좀비가 이동하는 부분
여기서 moveMap에 다음위치를 복사, map에서 좀비를 전부지우고 map에 moveMap의 좀비위치를 복사, moveMap의 좀비를 전부지우는 과정으로 진행
3-4. 좀비가 이동한뒤 아리와 만났는지 확인
구현하는 방법은 가지각색이겠으나, 필자처럼 은메모리공간에 덮어씌지 않도록 코드를 짜도록 유의하면될것같다.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//map
//빈공간 : 0
//아래방향 좀비 : 2
//위방향 좀비 : 3
//x : 아리의 행 인덱스 y : 아리의 열 인덱스
//moveMap : 좀비가 이동할때 잠시 기록하는 버퍼 역할
int n, x=0, y=0, **map, **moveMap, cnt=0;
//button : 스위치 위치 기록 light : 불빛이 비추는 곳 기록
bool **button, **light;
char c[51]; //아리가 움직일 명령
//아리가 좀비랑 마주치면 true리턴
bool action() { //해당위치에서의 행동을 실행
//1. 형광등확인
//현재위치에 스위치가있다면
if (button[x][y]) {
light[x][y] = true; //현재위치를 밝힘
//유효한범위의 불을 밝힘
if (y >= 1) light[x][y - 1] = true;
if (x >= 1 && y >= 1) light[x - 1][y - 1] = true;
if (x >= 1) light[x - 1][y] = true;
if (x >= 1 && y <= n - 2) light[x - 1][y + 1] = true;
if (y <= n - 2) light[x][y + 1] = true;
if (x <= n - 2 && y <= n - 2) light[x + 1][y + 1] = true;
if (x <= n - 2) light[x + 1][y] = true;
if (x <= n - 2 && y >= 1) light[x + 1][y - 1] = true;
button[x][y] = false; //현재 스위치 삭제
}
//2. 현재위치 좀비확인
//불이 꺼져있던경우에 좀비랑 마주쳤다면
if (!light[x][y] && (map[x][y] == 2 || map[x][y] == 3)) {
printf("Aaaaaah!");
return true;
}
//3-1. 좀비 이동 (1)
//moveMap에 복사
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 2) { //아래방향 좀비일때
if (i + 1 <= n - 1) { //유효한가?
moveMap[i + 1][j] = 2; //좀비 이동
}
else { //벽에닿은경우 (유효하지않은경우)
moveMap[i][j] = 3; //180도 방향전환
}
}
else if (map[i][j] == 3) { //위방향 좀비일때
if (i - 1 >= 0) {
moveMap[i - 1][j] = 3;
}
else {
moveMap[i][j] = 2;
}
}
}
}
//3-2. 좀비이동 (2)
//기존 map에서 좀비위치들만 전부 삭제
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (map[i][j] == 2 || map[i][j] == 3)
map[i][j] = 0;
//3-3. 좀비이동 (3)
//복사한 moveMap에서 map으로 복사, moveMap 초기화
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (moveMap[i][j] == 2 || moveMap[i][j] == 3) {
map[i][j] = moveMap[i][j]; //복사
moveMap[i][j] = 0; //초기화
}
//4. 좀비이동후 다시 아리가 잡혔는지 확인
if (!light[x][y] && (map[x][y] == 2 || map[x][y] == 3)) {
printf("Aaaaaah!");
return true;
}
return false;
}
//아리가 좀비랑 마주쳤다면 true리턴
bool playGame() {
//아래 1 왼쪽 2 위 3 오른쪽 4
int view_dir = 1;
for (int i = 0; i < cnt; i++) {
char order = c[i];
if (order == 'F') {
if (view_dir == 1) {
if (x + 1 < n) //이동가능한경우만
x++;
}
else if (view_dir == 2) {
if (y - 1 > -1)
y--;
}
else if (view_dir == 3) {
if (x - 1 > -1)
x--;
}
else if (view_dir == 4) {
if (y + 1 < n)
y++;
}
}
else if (order == 'L') { //왼쪽으로 방향을 튼다
view_dir--;
if (view_dir == 0)
view_dir = 4;
}
else if (order == 'R') { //오른쪽으로 방향을 튼다
view_dir++;
if (view_dir == 5)
view_dir = 1;
}
//행동을 함
if (action()) //만약 기절했다면 게임종료
return true;
}
return false;
}
int main(void) {
scanf("%d%s", &n, &c);
map = new int* [n]; //맵
moveMap = new int* [n];
light = new bool* [n]; //형광등맵
button = new bool* [n]; //스위치 위치 기록
for (int i = 0; i < n; i++) {
map[i] = new int[n];
moveMap[i] = new int[n];
light[i] = new bool[n];
button[i] = new bool[n];
char temp[16];
scanf("%s", &temp);
for (int j = 0; j < n; j++) {
moveMap[i][j] = 0;
light[i][j] = false;
button[i][j] = false;
if (temp[j] == 'O') { //빈공간
map[i][j] = 0;
}
else if (temp[j] == 'S') { //형광등
button[i][j] = true;;
}
else if (temp[j] == 'Z') { //좀비
map[i][j] = 2; //처음엔 모두 아래를 보고있다.
}
}
}
//명령어의 총갯수를 셈
for (int i = 0; i < 51; i++)
if (c[i] == '\0')
break;
else
cnt++;
if (!playGame()) //아리가 좀비를피해 살아남았다면 false리턴
printf("Phew...");
return 0;
}