BFS(너비 우선 탐색)

pseudo code

BFS(G, s)
for each vertex u (G.V에서 s를 제외한 모든 노드)
u.color = WHITE;
u.d = MAX;
u.prev = NULL;
s.color = GRAY;
s.d = 0;
s.prev = NULL;
Q 초기화;
ENQUEUE(s);
while Q가 공집합이 아닌 동안
u = DEQUEUE(Q);
for each v(u와 연결된 v에 대하여)
{
if (v.color == WHITE)
{
v.color = GRAY;
v.d = u.d + 1;
v.prev = NULL;
ENQUEUE(Q, v);-> 그레이로 바꾸고 큐에 넣는 이유, 한번 더 들어갈 수 있기 때문
}
}
u.color = BLACK;

활용 문제

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

[내 코드]

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

typedef struct point
{
	int row;
	int col;
}Point;

int main()
{
	int i, j, N, M;
	scanf("%d %d ", &N, &M);

	char** maze = (char**)calloc((N + 2),(sizeof(char*)));
	for (i = 0; i <= N + 1; i++)
	{
		maze[i] = (char*)calloc((M + 2),(sizeof(char)));
	}

	for (i = 1; i <= N; i++)
	{
		scanf("%s", maze[i] + 1); // 1칸 더 뒤에 가능??
	}

	int step[102][102] = {0};

	for (i = 0; i <= N + 1; i++)
	{
		step[i][0] = 1;
		step[i][M + 1] = 1;
	}

	for (j = 0; j <= M + 1; j++)
	{
		step[0][j] = 1;
		step[N + 1][j] = 1;
	}

	Point queue[10001];
	int start = -1;
	int finish = -1;

	queue[++start].row = 1;
	queue[start].col = 1;

	step[1][1] = 1;

	while (start != finish)
	{
		Point temp;
		temp.row = queue[++finish].row;
		temp.col = queue[finish].col;

		if (!step[temp.row][temp.col - 1] && maze[temp.row][temp.col - 1] == '1') // 왼쪽
		{
			queue[++start].row = temp.row;
			queue[start].col = temp.col - 1;

			step[temp.row][temp.col - 1] = step[temp.row][temp.col] + 1;
		}

		if (!step[temp.row][temp.col + 1] && maze[temp.row][temp.col + 1] == '1') // 오른쪽
		{
			queue[++start].row = temp.row;
			queue[start].col = temp.col + 1;

			step[temp.row][temp.col + 1] = step[temp.row][temp.col] + 1;
		}

		if (!step[temp.row - 1][temp.col] && maze[temp.row - 1][temp.col] == '1') // 위
		{
			queue[++start].row = temp.row - 1;
			queue[start].col = temp.col;

			step[temp.row - 1][temp.col] = step[temp.row][temp.col] + 1;
		}

		if (!step[temp.row + 1][temp.col] && maze[temp.row + 1][temp.col] == '1') // 아래
		{
			queue[++start].row = temp.row + 1;
			queue[start].col = temp.col;

			step[temp.row + 1][temp.col] = step[temp.row][temp.col] + 1;
		}	
	}

	printf("%d", step[N][M]);

	return 0;
}

Tip.
문자열은 char배열의 어느 한 칸의 주소를 가리켜 입력할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	char array[100];
	scanf("%s", array + 1);

	printf("%s", array + 1);
	return 0;
}