2178번: 미로 탐색

2178번: DFS와 BFS(BOJ C/C++)

사용 언어: C

 

문제

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

 

풀이

x와 y 좌표가 존재하므로 바로 구조체로 int x, int y를 만든다. 문제를 보면 모든 방향으로 검사해야하므로 당연히 BFS를 쓰면 되고, 많이 고민했던 부분이 모든 방향으로 어떻게 검사할지였다 -> (+1,0),(-1,0),(0,+1),(0,-1). 그래서 이 부분은 다른 분들의 코드를 조금 참고했는데 생각보다 너무 단순해서.... 후 이게 끝나면 BFS 구현이 남는데 그냥 큐와 방문한 곳을 사용하면 쉽게 쓸 수 있다. 하나 더 검색해본 것이 있는데 그것은 입력을 띄어쓰기를 안 받고 받아서 '각 정수를 입력받을때마다 %10하면서 배열에 입력해야하나?' 생각을 했지만 그럴리가 없을 것 같아서 검색해보니 %1d.... 기본이 부족한건가 ㅠ 다음부턴 꼭 기억하고 써먹자!

#include <stdio.h>
#define MAX 101
#define BIG 10000

int graph[MAX][MAX];
int visited[MAX][MAX];
int M,N;

typedef struct Node{
	int x;
	int y;
}q;

q queue[BIG+1];
int rear = 0;
int front = 0;
int max = 0;

int vectX[4] = {0,0,1,-1};
int vectY[4] = {1,-1,0,0};

q dequeue()
{
    q temp = queue[front];
    front = (front + 1) % BIG;
    return temp;
}

void enqueue(int x, int y)
{
    q temp;
    temp.x = x;
    temp.y = y;
    queue[rear] = temp;
    rear = (rear + 1) % BIG;
}

void BFS()
{
	int nextX, nextY;
	while(front<rear)
	{
		q pop=dequeue();
		for(int i=0;i<4;i++) //모든 방향으로 검사
		{
			nextX = vectX[i] + pop.x;
			nextY = vectY[i] + pop.y;
			
			if(nextX>=1 && nextX<=M && nextY>=1 && nextY<=N)
				if(graph[nextX][nextY] && !visited[nextX][nextY])
				{
					//(M,N)에 도착하는 값이 항상 최소, 그 외의 값은 첫 if 조건에서 이미 걸러짐.
					visited[nextX][nextY] = visited[pop.x][pop.y]+1;
					enqueue(nextX,nextY);
				}
		}
	}
}

int main(void)
{
	scanf("%d %d", &M, &N);
    for(int i=1; i<=M; i++)
        for(int j=1; j<=N; j++)
            scanf("%1d", &graph[i][j]); //하나씩 입력 받음
	visited[1][1] = 1;
    enqueue(1, 1);
    BFS();
    printf("%d\n", visited[M][N]);
}