[백준 문제 C++] 3109 빵집

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

3109번: 빵집

#include <stdio.h>
#include <stdlib.h> //system("pause") 쓰기 위한 라이브러리

char map[10000][501]; //char 배열은 마지막 null 문자 들어가야되서 크기 + 1
int used[10000][500];
int dirR[3] = { -1, 0, 1 };

int maxRow, maxCol;
int result;
bool finished;

//현재 진행 상태를 볼 수 있게 만든 함수
void PrintState()
{
	printf("\n");
	for (int i = 0; i < maxRow; ++i)
	{
		for (int j = 0; j < maxCol; ++j)
		{
			if (map[i][j] == 'x')
			{
				printf("x");
				continue;
			}
			printf("%d", used[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	system("pause"); // 키를 누를 때까지 멈춤
}

void DFS(int row, int col, int num) //Depth First Search
{
	//PrintState(); //dfs 탐색 순서를 보고 싶다면 주석 제거

	if (col == maxCol - 1)
	{
		result++;
		finished = true;
		return;
	}

	int nextCol = col + 1;
    
	for (int i = 0; !finished && i < 3; ++i)
	{
		int nextRow = row + dirR[i];

		if (0 <= nextRow && nextRow < maxRow &&
			map[nextRow][nextCol] == '.' &&
			used[nextRow][nextCol] == 0)
		{
			used[nextRow][nextCol] = num;
			DFS(nextRow, nextCol, num);
		}
	}
}

int main()
{
	scanf("%d %d", &maxRow, &maxCol);

	for (int i = 0; i < maxRow; ++i)
	{
		scanf("%s", map[i]);
	}

	for (int i = 0; i < maxRow; ++i)
	{
		finished = false;
		used[i][0] = i + 1;

		DFS(i, 0, i + 1);
	}

	PrintState(); //탐색 완료 된 형태 출력
	printf("%d\n", result);
}

깊이 우선 탐색이 필요한 문제였다.

그리고 탐색이 성공하면 기존의 탐색도 반드시 종료시켜야 된다.

이걸 안해주면 다음과 같은 상황이 발생하게 된다..

지 혼자 모든 곳을 다 점령해버린다.

 

ex) 4x4

   1111

   xx11

   xxx1

   xxxx

 

이를 위해 전역변수로 bool finished를 선언해주었고,

탐색 전에 finished = false,

탐색이 성공하면 finished를 true로 변경해준다.

 

DFS for문의 조건이 finished == false && i < 3 으로 되어있기에

한 번이라도 마지막 지역에 도착했다면 다른 탐색을 하지 않을 수 있게 된다.