[G2] 백준 3109번 빵집 C++ 깊이 우선 탐색, 그리디 알고리즘

리뷰

 

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

맵의 범위가 10000 * 500으로 DFS를 활용할 경우 시간 초과가 날 것을 우려했다.

하지만 파이프라인의 경로가 겹칠 수 없다는 조건이 있기에 그리디 하게 문제를 풀이할 수 있었다.

 

 

전역 변수

1. r : 맵의 세로 길이를 저장할 정수형 변수
2. c : 맵의 가로 길이를 저장할 정수형 변수
3. ans : 정답을 저장하고 출력하기 위한 정수형 변수
4. lst : 맵 정보를 저장하기 위한 문자열 타입의 배열
5. v : 방문 정보를 저장하기 위한 논리형 2차 배열
6. dx, dy : 우상향, 우향, 우하향을 진행하기 위한 방향 배열

 

함수

1. dfs

bool dfs(int cx, int cy)

 

깊이 우선 탐색을 통해 가스관부터 빵집 까지의 파이프라인 연결이 가능한지를 체크하기 위한 함수

1. 매개 변수로 현재 좌표의 위치 cx, cy를 전달받는다.
2. 기저 조건으로 cy가 만약  c - 1에 도달하였다면, true를 리턴해 준다.
3. 3방향 탐색을 시작, 다음 위치가 맵의 범위 안에 있으며, 방문 처리 되지 않았고, 맵 상에서 '.'라면 이동을 진행한다.
4. 이동한 위치에 방문 처리를 진행한 후 이동한 위치에서 dfs함수를 진행하고 리턴값이 true라면 true를 리턴한다.
5. 위 두 조건에서 true로 리턴되지 못한 경우 최종적으로 false를 리턴해 준다.

 

문제풀이

1. r, c의 값을 입력 받고, r개의 문자열로 이루어진 맵 정보를 lst배열에 입력 받아준다.
2. 각 행을 순회하며 첫번재 열로 부터 dfs함수를 수행하고, 리턴 값이 true라면 ans를 증가시킨다.
3. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 맵의 좌상단부터 시작하여 방향 배열도 우상향, 우향, 우하향 순으로 탐색해야 그리디한 풀이가 가능하다.
• 잘못된 경로로 탐색한 경우에도 재귀를 빠져나온 후 방문 처리를 유지해 주어야 그리디한 풀이가 가능하다.
• 위 조건에 맞추어 본다면 최대 10000 * 500번의 탐색으로 문제 풀이가 가능하다.

 

정답 코드

#include<iostream>
using namespace std;

int r, c, ans;
string lst[10000];
bool v[10000][500];
int dx[] = { -1, 0, 1 };
int dy[] = { 1, 1, 1 };

bool dfs(int cx, int cy) {
	if (cy == c - 1) return true;
	for (int i = 0; i < 3; ++i) {
		int nx = cx + dx[i], ny = cy + dy[i];
		if (0 <= nx && nx < r && 0 <= ny && ny < c && !v[nx][ny] && lst[nx][ny] == '.') {
			v[nx][ny] = true;
			if (dfs(nx, ny)) return true;
		}
	}
	return false;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> r >> c;
	for (int i = 0; i < r; ++i) cin >> lst[i];

	for (int i = 0; i < r; ++i) {
		if (dfs(i, 0)) ans++;
	}
	cout << ans;
}