[C언어] 백준 2178 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

예제 입력 1 

4 6
101111
101010
101011
111011

예제 출력 1 

15

예제 입력 2 

4 6
110110
110110
111111
111101

예제 출력 2 

9

예제 입력 3 

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3 

38

예제 입력 4 

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4 

13

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

2178번: 미로 탐색

 

BFS 알고리즘하면 빼놓을 수 없는 최단 거리 측정하는 미로 탐색 문제입니다.

머리로 구현하기는 쉽지만 막상 구현하려면 시간이 좀 걸리는 문제인데요.

맵을 y, x만큼 받고 1, 1에서부터 시작해서 우측 하단까지 걸리는 최단 거리를 보는 문제입니다.

당연하게도 1, 1에서 시작하는 캐릭터는 상하좌우로만 움직일 수 있으며 벽 통과는 안됩니다.

 

1, 1부터 시작해서 우측 하단까지 최단거리를 재는거니까 현재 위치서부터

상하좌우를 살펴 가장 짧은 거리를 탐색해 + 1 하는 방식으로 풀었습니다.

 

저는 이 문제를 큐 자료구조를 사용해서 풀었고 큐는 양방향 링크드 리스트로 만들었습니다.

typedef struct n
{
    int ny;
    int nx;
    struct n *next;
    struct n *prev;
} node;

node *head, *tail, *n;

node *create_node(int ny, int nx)
{
    node *t;

    t = (node *)malloc(sizeof(node));
    t->nx = nx;
    t->ny = ny;
    t->next = NULL;
    t->prev = NULL;
    return (t);
}

void    create_queue(void)
{
	head = create_node(-1, -1);
	tail = create_node(-1, -1);
	head->next = tail;
	tail->prev = head;
}

void    push(int ny, int nx)
{
    node *last;
    node *t;

    last = tail->prev;
    t = create_node(ny, nx);
    last->next = t;
    t->prev = last;
    t->next = tail;
    tail->prev = t;
}

node *pop(void)
{
    node *f;
    node *s;

    f = head->next;
    s = f->next;
    head->next = s;
    s->prev = head;
    return (f);
}

void    insert(int ny, int nx)
{
    if (ny - 1 >= 0 && map[ny - 1][nx] != 0)
        push(ny - 1, nx);
    if (ny + 1 < y && map[ny + 1][nx] != 0)
        push(ny + 1, nx);
    if (nx - 1 >= 0 && map[ny][nx - 1] != 0)
        push(ny, nx - 1);
    if (nx + 1 < x && map[ny][nx + 1] != 0)
        push(ny, nx + 1);
}

void node_free(node *t)
{
    if (t->next != NULL)
        node_free(t->next);
    free(t);
}

노드안에 y, x값을 넣게 설정했고 create_queue함수로 큐를 만들고 create_node함수로 이어줄 노드를 만들게끔 설정했습니다.

현재 위치를 기준으로 상하좌우를 보며 다음 위치가 벽이 아니라면 push를하고 리스트를

다 썼을 때 동적할당 해제하는 free함수를 만들었습니다.

마지막으로 기본적인 push와 pop함수 두개만 만들어 사용했습니다.

 

int y, x;
int **map, **visited;

int min(int ny, int nx)
{
    int min = 2147483647;

	// 네 방향 중 가장 값이 작은곳 찾기
    if (ny + 1 < y && map[ny + 1][nx] < min && map[ny + 1][nx] != 0 && map[ny + 1][nx] != 1)
        min = map[ny + 1][nx];
    if (ny - 1 >= 0 && map[ny - 1][nx] < min && map[ny - 1][nx] != 0 && map[ny - 1][nx] != 1)
        min = map[ny - 1][nx];
    if (nx + 1 < x && map[ny][nx + 1] < min && map[ny][nx + 1] != 0 && map[ny][nx + 1] != 1)
        min = map[ny][nx + 1];
    if (nx - 1 >= 0 && map[ny][nx - 1] < min && map[ny][nx - 1] != 0 && map[ny][nx - 1] != 1)
        min = map[ny][nx - 1];
	// 네 방향 모두 벽이라면
    if (min == 2147483647)
        min = map[ny][nx];
    return (min);
}

상하좌우를 살펴 최단거리 측정을 하는 min함수 입니다.

만약 네 방향 모두 벽일 시 그냥 현 위치값을 넣게끔 설정했습니다.

 

int promising(int ny, int nx)
{
    if (nx < 0 || nx >= x || ny < 0 || ny >= y)
        return (0);
	// 벽이거나 이미 방문했었다면
    if (!map[ny][nx] || visited[ny][nx])
        return (0);
    visited[ny][nx] = 1;
    return (1);
}

유망성 체크하는 promising 함수 입니다.

현위치가 맵을 벗어났거나 벽이거나 이전에 방문한적이 있다면 0을 리턴하고

유망하다면 1을 리턴합니다.

 

void    init(void)
{
    create_queue();
    map = (int **)malloc(sizeof(int *) * y);
    visited = (int **)malloc(sizeof(int *) * y);
    for(int i = 0; i < y; i++)
    {
        map[i] = (int *)malloc(sizeof(int) * x);
        visited[i] = (int *)malloc(sizeof(int) * x);
    }
    for(int i = 0; i < y; i++)
    {
        for(int j = 0; j < x; j++)
            scanf("%1d", &map[i][j]);
    }
    for(int i = 0; i < y; i++)
    {
        for(int j = 0; j < x; j++)
            visited[i][j] = 0;
    }
    map[0][0] = 1;
    visited[0][0] = 1;
    push(1, 0);
    push(0, 1);
}

맨 처음 bfs를 실행하기 전 모든 변수들을 초기화 시켜줄 init 함수입니다.

1, 1 부터 시작하니까 처음 위치를 1로 초기화 해주고(사실 안해줘도 상관은 없을것 같지만 일단 해줬습니다)

처음 위치에서 갈 수 있는곳은 아래와 오른쪽 뿐이기에 두 곳을 push 해줬습니다.

 

int main(void)
{
    scanf("%d %d", &y, &x);
    init();
    while (map[y - 1][x - 1] == 1)
    {
        n = pop();
        if (!promising(n->ny, n->nx))
        {
            free(n);
            continue ;
        }
        insert(n->ny, n->nx);
        map[n->ny][n->nx] = min(n->ny, n->nx) + 1;
        free(n);
    }
    node_free(head);
    printf("%d\n", map[y - 1][x - 1]);
    return (0);
}

마지막 main함수입니다.

bfs 실행 전 init해서 모든 변수를 초기화 해주고 맵의 우측 하단이 1일 때까지 반복 시켰습니다.

promising으로 현 위치를 유망성 체크해서 잘 못된경우 바로 다음으로 넘어가고

유망하다면 현 위치에서 네 방향 넣어줄 insert함수를 호출합니다.

그리고 현 위치를 min함수를 이용해 + 1 해서 한칸 움직였다는 표시를 해주면서 반복하게끔 설정했습니다.

 

이렇게 bfs가 끝나면 동적할당 해준걸 해제시키고 출력 시킨뒤 프로그램이 끝납니다.

 

 

 

전에 42 서울에서 so_long이란 미니 2D 게임을 만드는 과제를 했었는데 그때 적을 만드는 부분이 있었습니다.

그때 적이 플레이어를 따라오게끔 설정을 하다보니 bfs알고리즘을 완벽하게 이해하게 되버려서 생각보다 쉽게 풀었네요

 

비록 코드는 길지만 나름 잘 풀었다고 생각됩니다.

 

 

반응형

전체 코드

#include <stdio.h>
#include <stdlib.h>

typedef struct n
{
    int ny;
    int nx;
    struct n *next;
    struct n *prev;
} node;

node *head, *tail, *n;
int y, x;
int **map, **visited;

node *create_node(int ny, int nx)
{
    node *t;

    t = (node *)malloc(sizeof(node));
    t->nx = nx;
    t->ny = ny;
    t->next = NULL;
    t->prev = NULL;
    return (t);
}

void    create_queue(void)
{
	head = create_node(-1, -1);
	tail = create_node(-1, -1);
	head->next = tail;
	tail->prev = head;
}

void    push(int ny, int nx)
{
    node *last;
    node *t;

    last = tail->prev;
    t = create_node(ny, nx);
    last->next = t;
    t->prev = last;
    t->next = tail;
    tail->prev = t;
}

node *pop(void)
{
    node *f;
    node *s;

    f = head->next;
    s = f->next;
    head->next = s;
    s->prev = head;
    return (f);
}

void    insert(int ny, int nx)
{
    if (ny - 1 >= 0 && map[ny - 1][nx] != 0)
        push(ny - 1, nx);
    if (ny + 1 < y && map[ny + 1][nx] != 0)
        push(ny + 1, nx);
    if (nx - 1 >= 0 && map[ny][nx - 1] != 0)
        push(ny, nx - 1);
    if (nx + 1 < x && map[ny][nx + 1] != 0)
        push(ny, nx + 1);
}

int promising(int ny, int nx)
{
    if (nx < 0 || nx >= x || ny < 0 || ny >= y)
        return (0);
	// 벽이거나 이미 방문했었다면
    if (!map[ny][nx] || visited[ny][nx])
        return (0);
	visited[ny][nx] = 1;
    return (1);
}

void    init(void)
{
    create_queue();
	map = (int **)malloc(sizeof(int *) * y);
	visited = (int **)malloc(sizeof(int *) * y);
	for(int i = 0; i < y; i++)
	{
		map[i] = (int *)malloc(sizeof(int) * x);
		visited[i] = (int *)malloc(sizeof(int) * x);
	}
    for(int i = 0; i < y; i++)
    {
        for(int j = 0; j < x; j++)
            scanf("%1d", &map[i][j]);
    }
	for(int i = 0; i < y; i++)
	{
		for(int j = 0; j < x; j++)
			visited[i][j] = 0;
	}
    map[0][0] = 1;
	visited[0][0] = 1;
    push(1, 0);
    push(0, 1);
}

int min(int ny, int nx)
{
    int min = 2147483647;

	// 네 방향 중 가장 값이 작은곳 찾기
    if (ny + 1 < y && map[ny + 1][nx] < min && map[ny + 1][nx] != 0 && map[ny + 1][nx] != 1)
        min = map[ny + 1][nx];
    if (ny - 1 >= 0 && map[ny - 1][nx] < min && map[ny - 1][nx] != 0 && map[ny - 1][nx] != 1)
        min = map[ny - 1][nx];
    if (nx + 1 < x && map[ny][nx + 1] < min && map[ny][nx + 1] != 0 && map[ny][nx + 1] != 1)
        min = map[ny][nx + 1];
    if (nx - 1 >= 0 && map[ny][nx - 1] < min && map[ny][nx - 1] != 0 && map[ny][nx - 1] != 1)
        min = map[ny][nx - 1];
	// 네 방향 모두 벽이라면
	if (min == 2147483647)
		min = map[ny][nx];
    return (min);
}

void node_free(node *t)
{
    if (t->next != NULL)
        node_free(t->next);
    free(t);
}

int main(void)
{
    scanf("%d %d", &y, &x);
    init();
    while (map[y - 1][x - 1] == 1)
    {
        n = pop();
        if (!promising(n->ny, n->nx))
        {
            free(n);
            continue ;
        }
        insert(n->ny, n->nx);
        map[n->ny][n->nx] = min(n->ny, n->nx) + 1;
        free(n);
    }
    node_free(head);
    printf("%d\n", map[y - 1][x - 1]);
    return (0);
}