[백준] 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

티스토리툴바