BOJ 3109

05 Feb 2020 • ProblemSolving

빵집

문제출처

문제 해석

  • 1열과 C열을 연결할 수 있는 최대 가스관 수를 구하는 문제입니다.
  • 빵집과 가스관 사이에는 건물이 있을 수 있고, 건물이 있으면 가스관을 놓을 수 없습니다.
  • 한 칸에 하나의 가스관만 지나갈 수 있습니다.

설계(10)

  • 해당 문제는 1열에서 시작해서 C열에 도착할 수 있는지 여부를 dfs로 탐색하였습니다.
  • 그리고 순서대로 오른쪽위, 오른쪽, 오른쪽 아래 순으로 탐색하여 최대한 위부터 가스관을 채우는 그리디 방식으로 구현하였습니다.

구현(50)

코드1
#include <iostream>
using namespace std;
#define MAXN 10000
int dx[] = { -1,0,1 };
int dy[] = { 1,1,1 };

char map[MAXN][500];
bool visited[MAXN][500];
int R, C;
bool flag;
bool is_range(int x, int y) {
	return (x >= 0 && y >= 0 && x < R && y < C);
}
int ans = 0;
void dfs(int x, int y) {
	if (flag) return;
	if (y == C-1) {
		ans++;
		flag = true;
		return;
	}
	visited[x][y] = true;
	int ret = 0;
	for (int k = 0; k < 3; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (!is_range(nx, ny) || visited[nx][ny]) continue;
		if (map[nx][ny] == 'x') continue;
		dfs(nx, ny);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		cin >> map[i];
	}
	
	for (int i = 0; i < R; i++) {
		flag = false;
		dfs(i, 0);
	}
	
	cout << ans << "\n";
	return 0;
}
코드2(최적화)
#include <iostream>
using namespace std;
#define MAXN 10000

int dx[] = { -1,0,1 };
int dy[] = { 1,1,1 };

char map[MAXN][500];
bool visited[MAXN][500];

int R, C;
bool flag;

int ans = 0;
bool dfs(int x, int y) {
	if (map[x][y] != '.') return 0;
	if (y == C - 1) return 1;
	map[x][y] = 'x';
	return dfs(x - 1, y + 1) || dfs(x, y + 1) || dfs(x + 1, y + 1);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		cin >> map[i];
	}

	for (int i = 0; i < R; i++) {
		ans += dfs(i, 0);
	}
	cout << ans << "\n";
	return 0;
}
디버깅
  • 처음에는 한번의 백트래킹으로 모든 행을 탐색을 하되, 마지막 열에 도착한 경우 방문표시를 유지하고 중간에 끊긴 경우 방문체크를 해제하도록 구현하려고 했습니다.
  • 그러나, 다시 생각해본 결과 중간에 끊긴 경로의 방문한 경로로는 다음 행에서도 갈 수 없다고 판단하여, dfs로 변환을 시켰습니다.
  • 또한 모든 행을 한번에 탐색하지 않고, 한 행마다 탐색하도록 변경하였습니다.
제출결과
  • 80ms

마무리

  • 공개코드 처리된 qse1346님의 코드는 재귀함수를 아주 깔끔하게 짜셔서 참조하기위해 재 구현해봤습니다.
  • 좌표를 직접 매개변수로 보내고 or연산 이용하여 모든 경로를 탐색하도록 하였고, 방문체크 배열을 사용하는 대신에 다른 문자로 변환하여 사용한 점이 아주 인상적이었습니다.
  • 이와같이 재귀함수를 깔끔하게 짜서 혼동을 일으키지 않도록 해야할 것 같습니다.
 BOJ

Related Posts