백준 3109 빵집

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

3109번: 빵집

 

그리디 알고리즘 문제다.

 

처음엔 DP를 끝에서부터 하다가 실패해서

그리디 알고리즘으로 다시 했다.

 

아이디어는 '성공할 수 있는 경로는 누가 와도 성공할 수 있다.'이다.

 

예를 들어서

 

.xx..
..x..
.....
...x.
...x.

 

문제는 다음과 같은 예시를 제공한다. 첫 행의 네 번째 열의 .까지 도착하면 바로 성공할 수 있다.

출발점이 무엇이든간에 저기에 도착하면 성공한다. 

 

마찬가지로 성공으로 갈 수 있는 경로는 누가 가더라도 성공한다. 단, 그 경로에 접근할 수 있는지 없는지를 판단해야한다. 그렇기 때문에 Greedy Algorithm을 쓸 수 있다. 만약 진행중인 Path가 벽에 가로막혀서 더 이상 진행할 수 없다면 그 Path는 누가와도 성공할 수 없는 Path이다. 그러므로 없는 셈 쳐도 된다. 

 

/* 빵집 */

#include <iostream>

#define WALL 'x'
#define EMPTY '.'
#define MAXR 10010
#define MAXC 510

using namespace std;

int R, C, Ans;
int dr[3] = { -1, 0, 1 };

char map[MAXR][MAXC];

void input();
void solve();

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();
	solve();

	return 0;

}

void input() {
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
		}
	}
}

inline bool is_range(int r, int c) {
	return r >= 0 && r < R&& c >= 0 && c < C;
}

bool b_t(int r, int c) {
	if (is_range(r, c) == false) return false;
	if (map[r][c] == WALL) return false;
	map[r][c] = WALL;

	if (c == C - 1) return true;

	if (b_t(r - 1, c + 1) == true) return true;
	if (b_t(r, c + 1) == true) return true;
	if (b_t(r + 1, c + 1) == true) return true;
	return false;
}

void solve() {
	for (int i = 0; i < R; i++) {
		if (b_t(i, 0) == true) Ans++;
	}
	cout << Ans << '\n';
	return;
}

 

간단하다. A가 갈 수 없다면 B도 갈 수 없다. A가 갈 수 있으면 B도 갈 수 있다. 그렇기 때문에 Back Tracking 알고리즘이지만 map[r][c] = WALL로 할당한 값을 바꾸는 코드가 없다. 실패했다면, 다시 그 경로를 탐색할 필요가 없기 때문에 WALL을 할당한 다음 되돌리지 않는다. 

 

https://hsin.hr/2009/

Croatian Highschool Competitions in Informatics 2009

 

National Competition #1 23th March 2009 Juniors 세번째 문제다. 참고하시길!