[백준] 3109. 빵집 - C++ — 젝무의 개발새발

[Gold II]

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

3109번: 빵집

유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던

www.acmicpc.net

풀이

우선, 찬찬히 살펴보면,

첫 번째 열의 모든 칸에서부터, 최대한 많이 마지막 열의 칸으로 연결해야 한다.

이 때, Greedy하게 첫째 열의 맨 위(첫 번째) 칸에서부터 시작해도 되며,

오른쪽 위 / 오른쪽 / 오른쪽 아래 3개의 선택지 중, 오른쪽 위를 선택하는 것이 이후 파이프 연결에서 가장 유리하므로, 또한 Greedy하게 오른쪽 위 - 오른쪽 - 오른쪽 아래 순으로, 가능한 선택지를 바로 고르는 것이 좋다.

따라서 수도 코드로 간단하게 표현하자면 아래와 같이 진행하게 되는 것이다.

 for 모든 첫째 열의 칸들에 대해:
  while 마지막 열에 갈 때까지:
    if 오른쪽 위가 비어있다면:
      오른쪽 위를 선택
    elif 오른쪽이 비어있다면:
      오른쪽을 선택
    elif 오른쪽 아래가 비어있다면:
      오른쪽 아래를 선택
    else:
      이 루트 폐기

첫 시도는 TLE.

 #include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
#define init cin.tie(0)->ios_base::sync_with_stdio(0);
 
using namespace std;
 
bool M[10001][501] = {};
 
bool dfs(int i, int j, int R, int C) {
    // 칸을 넘어가면 false, 마지막 열일 시 true. (기저조건)
    if (i < 0 || i >= R || j < 0 || j >= C) return false;
    if (!M[i][j]) return false;
    if (j == C - 1) return true;
 
    // 우측 위, 우측, 우측 아래 순으로 dfs 호출.
    if (dfs(i - 1, j + 1, R, C))
        M[i][j] = false;
    else if (dfs(i, j + 1, R, C))
        M[i][j] = false;
    else if (dfs(i + 1, j + 1, R, C))
        M[i][j] = false;
    else
        return false;
 
    return true;
}
 
int main() {
    init;
 
    int R, C;
    cin >> R >> C;
    char ch;
 
    int result = 0;
 
    // 입력
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> ch;
            if (ch == '.') M[i][j] = true;
        }
    }
 
    for (int i = 0; i < R; i++) {
        if (dfs(i, 0, R, C)) result++;
    }
 
    cout << result;
}

풀이 2

시간 초과가 나 생각해 보니, 아래 부분에서, "마지막 열 도달에 성공했을 때" 만 방문 체크를 해 주었는데,

만약 마지막 열 도달에 실패했을 때에도, 그 칸에서 뻗어나가는 것은 항상 마지막 열에 도달하지 못한다는 것을 뜻한다.

그러므로, 마지막 열 도달에 실패해도, 방문 체크를 한다면 지수적으로 Time Complexity가 증가하지 않으므로 풀릴 것이라 생각했다.

 // 우측 위, 우측, 우측 아래 순으로 dfs 호출.
if (dfs(i - 1, j + 1, R, C))
    M[i][j] = false;
else if (dfs(i, j + 1, R, C))
    M[i][j] = false;
else if (dfs(i + 1, j + 1, R, C))
    M[i][j] = false;
else
    return false;

굉장히 빠르게 AC!

실력이 좀 늘었나...? 히히

 #include <algorithm>
#include <iostream>
#include <set>
#include <string>
#include <vector>
#define init cin.tie(0)->ios_base::sync_with_stdio(0);
 
using namespace std;
 
bool M[10001][501] = {};
 
bool dfs(int i, int j, int R, int C) {
    // 칸을 넘어가면 false, 마지막 열일 시 true. (기저조건)
    if (i < 0 || i >= R || j < 0 || j >= C) return false;
    if (!M[i][j]) return false;
    if (j == C - 1) return true;
 
    // 우측 위, 우측, 우측 아래 순으로 dfs 호출.
    if (dfs(i - 1, j + 1, R, C)) {
        M[i][j] = false;
        return true;
    }
    if (dfs(i, j + 1, R, C)) {
        M[i][j] = false;
        return true;
    }
    if (dfs(i + 1, j + 1, R, C)) {
        M[i][j] = false;
        return true;
    }
    M[i][j] = false;
    return false;
}
 
int main() {
    init;
 
    int R, C;
    cin >> R >> C;
    char ch;
 
    int result = 0;
 
    // 입력
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> ch;
            if (ch == '.') M[i][j] = true;
        }
    }
 
    for (int i = 0; i < R; i++) {
        if (dfs(i, 0, R, C)) result++;
    }
 
    cout << result;
}

풀이
풀이 2

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

[백준] 3109. 빵집 - C++

풀이

풀이 2

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

	for 모든 첫째 열의 칸들에 대해:
	while 마지막 열에 갈 때까지:
	if 오른쪽 위가 비어있다면:
	오른쪽 위를 선택
	elif 오른쪽이 비어있다면:
	오른쪽을 선택
	elif 오른쪽 아래가 비어있다면:
	오른쪽 아래를 선택
	else:
	이 루트 폐기

	#include <algorithm>
	#include <iostream>
	#include <set>
	#include <string>
	#include <vector>
	#define init cin.tie(0)->ios_base::sync_with_stdio(0);

	using namespace std;

	bool M[10001][501] = {};

	bool dfs(int i, int j, int R, int C) {
	// 칸을 넘어가면 false, 마지막 열일 시 true. (기저조건)
	if (i < 0 \|\| i >= R \|\| j < 0 \|\| j >= C) return false;
	if (!M[i][j]) return false;
	if (j == C - 1) return true;

	// 우측 위, 우측, 우측 아래 순으로 dfs 호출.
	if (dfs(i - 1, j + 1, R, C))
	M[i][j] = false;
	else if (dfs(i, j + 1, R, C))
	M[i][j] = false;
	else if (dfs(i + 1, j + 1, R, C))
	M[i][j] = false;
	else
	return false;

	return true;
	}

	int main() {
	init;

	int R, C;
	cin >> R >> C;
	char ch;

	int result = 0;

	// 입력
	for (int i = 0; i < R; i++) {
	for (int j = 0; j < C; j++) {
	cin >> ch;
	if (ch == '.') M[i][j] = true;
	}
	}

	for (int i = 0; i < R; i++) {
	if (dfs(i, 0, R, C)) result++;
	}

	cout << result;
	}