[C언어] 백준 16954 움직이는 미로 탈출

문제

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

예제 입력 1 

Code

........
........
........
........
........
........
........
........

예제 출력 1 

Code

1

예제 입력 2 

Shell

........
........
........
........
........
........
##......
........

예제 출력 2 

Code

0

예제 입력 3 

Bash

........
........
........
........
........
.#......
#.......
.#......

예제 출력 3 

Code

0

예제 입력 4 

Code

........
........
........
........
........
.#######
#.......
........

예제 출력 4 

Code

1

예제 입력 5 

Code

........
........
........
........
#.......
.#######
#.......
........

예제 출력 5 

Code

0

 

https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

문제 풀기 전 로직 생각하기

---

.은 비어있는 곳, #은 벽 인 8 x 8 

# 인 벽이 한 사이클을 돌 때마다 한 칸씩 밑으로 내려 옵니다.

캐릭터는 항상 좌하단에 위치하며 출구는 항상 우상단에 위치합니다.

 

캐릭터가 출구 까지 이동 하는 방향은 인정한 한칸 즉 8방향과 제자리에 있게 할 수도 있습니다.

캐릭터가 먼저 움직인 뒤 벽이 내려오는 식이고 캐릭터와 벽이 겹치게 되면 안됩니다.

 

이 조건들을 살펴 봤을 때 기본 틀은 bfs로 잡고 캐릭터가 움직이기 전

벽이 먼저 내려오게끔 처리를 해서 이동할 수 있는 범위를 좁히면 좋을 것 같습니다.

 

또한 bfs로 push를 하게 된다면 8방향과 제자리 중 여러곳을 push하게 될 것입니다.

이렇게 되면 pop을 할 때마다 벽이 내려 오는 것이 아닌 무슨 조건을 주어야 할것 같습니다.

 

이러한 점들을 생각하면서 bfs의 조건을 큐가 빌 때 까지면서 출구 도달 유무를 조건으로 두면 될것 같습니다.

 

전체 코드

C++

#include <stdio.h>
#define INF 2147483647

typedef struct
{
    int		y;
    int		x;
	int		move_cnt;
}    queue;

queue    q[100000];
int cur_y, cur_x, last = 0, temp[9][9] = {};
char map[9][9];
// 8방향과 제자리 처리
int dx[9] = { -1, -1, -1, 0, 1, 1, 1, 0, 0 };
int dy[9] = { -1, 0, 1, 1, 1, 0, -1, -1, 0 };

int    is_in_map(int y, int x)
{
    if (0 <= x && x < 8 && 0 <= y && y < 8)
        return (1);
    return (0);
}

void    before_move_init()
{
	// 밑에서 부터 탐색
    for (int i = 7; i >= 0; i--)
    {
        for (int j = 7; j >= 0; j--)
        {
        	// 현재 좌표가 벽이면서 마지막 칸이 아니라면 벽 내려오게 처리
            if (temp[i][j] == -1 && i < 7)
                temp[i + 1][j] = -2;
        }
    }
}

void    after_move_init()
{
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
        	// 이전에 있던 벽 지우기
            if (temp[i][j] == -1)
                temp[i][j] = INF;
            // 내렸던 벽 초기화
            else if (temp[i][j] < -1)
                temp[i][j] = -1;
        }
    }
}

void    bfs()
{
    int nx, ny, cur = 0, tmp = 0, a = 0;

    q[last].y = 7;
    q[last].x = 0;
	q[last++].move_cnt = 0;
    // 출구를 방문하기 전이면서 큐가 빌 때까지
    while (cur < last && temp[0][7] == INF)
    {
        cur_y = q[cur].y;
        cur_x = q[cur].x;
        // 현재 걸음 수가 move_cnt와 같을 때
		if (q[cur++].move_cnt == tmp)
		{
        	// 한 번이라도 벽을 내린적이 있을 때 내렸던 벽 초기회
			if (a)
				after_move_init();
            // 벽 내리기
			before_move_init();
			a=1;
			tmp++;
		}
        // 현재 위치에서 8방향과 제자리 유망성 체크
        for (int i = 0; i < 9; i++)
        {
            ny = cur_y + dy[i];
            nx = cur_x + dx[i];
            if (is_in_map(ny, nx) && temp[ny][nx] == INF || (i == 8 && temp[ny][nx] == 0))
            {
                q[last].y = ny;
                q[last].x = nx;
				q[last++].move_cnt = tmp;
                temp[ny][nx] = 0;
            }
        }
    }
}

int main()
{
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            scanf("\n%c", &map[i][j]);
            temp[i][j] = INF;
            // 벽은 음수로 처리
            if (map[i][j] == '#')
                temp[i][j] = -1;
        }
    }
    temp[7][0] = 0;
    bfs();
    // 방문한 적이 없을 때
    if (temp[0][7] == INF || temp[0][7] < 0)
        printf("0\n");
    else
        printf("1\n");
    return (0);
}

 

문제 해설

---

따로 2차원 정수 배열을 선언해 준뒤 기본 값을 int_max로 줍니다.

벽은 따로 음수 처리를 해주고 bfs 함수로 들어갑니다.

 

bfs함수에서 풀기 전 로직 생각하기 부분에서 생각했던 내용들을 구현했습니다.

움직이기 전 벽을 미리 내려서 움직일 수 있는 방향을 좁히는 before_move_init 함수와

맵을 다시 초기화 해주는 after_move_init 함수를 만들었습니다. 

 

큐가 비어있지 않으면서 출구 도달 유무를 while 조건문으로 걸었고

걸음 수를 큐에 따로 값을 저장해 현재 걸음 수에 맞게 벽을 내리게끔 처리했습니다.

한번이라도 벽을 내린적이 있으면 맵을 다시 초기화를 해주게끔 했고

for 문으로 8방향과 제자리 유망성을 체크해서 push 해주었습니다.

 

이 과정을 반복 한 뒤 출구 도달 유무를 체크해서 0 또는 1을 출력하게 구현 했습니다.