[백준] 3109번: 빵집 (C++)

문제 링크

3109번: 빵집

---

그리디 문제집의 문제들을 살펴보다가, 재밌어 보이는 문제가 있어서 풀어보게 됐습니다.

처음에는 BFS로 풀면 되겠지하고 BFS로 풀어봤는데 모든 경우의 수를 탐색하는 것은 아니어서 틀렸습니다.

질문 게시판을 참고하니 DFS로 풀었다는 글이 다수여서 DFS로 풀었더니 시간초과가 발생했고,

vst 배열로 오른쪽 끝까지 갈 수 없는 길을 다시 가지 않도록 최적화했더니 겨우 통과가 되었습니다.

배낭문제같은 그리디 문제만 접하다가 이런 DFS를 활용한 그리디 문제를 접하게 되니 신기하고 재밌었습니다.

풀이

이 문제는 DFS + 그리디 문제이고, 지났던 길을 다시 탐색하지 않으면 됩니다.

문제를 요약하면, 왼쪽 끝에서 오른쪽 끝까지 3개의 방법으로(⬈, 🠮, ⬊) 갈 수 있는 최대의 경우의 수를 찾아야 합니다.

문제를 해결하려면 위(`[0][0]`)에서부터 아래(`[r - 1][0]`)까지 쭉 그리디를 진행해서 경우의 수를 찾아가면 됩니다.

1. 왼쪽 끝에서 오른쪽 끝에 도달할 때까지 DFS를 돌립니다.
2. 오른쪽 끝에 도달하면 경우의 수를 1 증가시킵니다.(`cnt++`)

풀이코드

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int r, c;
string s[10001];
bool vst[10001][501];
int dx[] = {-1, 0, 1};
int dy[] = {1, 1, 1};
bool isEnd = false;

void dfs(int x, int y) {
  vst[x][y] = true;

  if (y == c - 1) {
    isEnd = true;
    return;
  }

  for (int d = 0; d < 3; d++) {
    int nx = x + dx[d];
    int ny = y + dy[d];

    if (nx < 0 or nx >= r or ny < 0 or ny >= c) continue;
    if (s[nx][ny] != '.' or vst[nx][ny]) continue;
    dfs(nx, ny);
    if (isEnd) return;
  }
}

void solve() {
  cin >> r >> c;
  for (int i = 0; i < r; i++) cin >> s[i];

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

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

 

배운점

• 30번줄의 범위 체크하는 부분에서 맨 끝의 `ny`를 `nx`로 적어서 30분 이상 삽질(...)을 했습니다. 이런 실수가 다음에는 없도록 꼼꼼히 코드를 체크하는 습관을 들여야겠다고 생각했습니다.
• 일치하는 경우가 생기면 바로 값을 반환하고 DFS를 멈추는 기법을 배울 수 있었습니다. (33번줄)

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!