[백준 3109] 빵집 (C#, C++) - soo:bak

문제 링크

3109번 - 빵집

설명

첫 번째 열에서 마지막 열까지 서로 겹치지 않는 파이프 경로를 최대 몇 개 연결할 수 있는지 구하는 문제입니다.

접근법

각 행의 첫 번째 칸에서 출발하여 마지막 열까지 도달하는 경로를 찾습니다. 파이프는 오른쪽 위, 오른쪽, 오른쪽 아래 세 방향으로만 연결할 수 있습니다.

경로가 서로 겹치면 안 되므로 한 번 지나간 칸은 다시 사용할 수 없습니다. 위쪽 행부터 차례로 경로를 찾되, 각 칸에서 오른쪽 위를 먼저 시도하고, 안 되면 오른쪽, 그 다음 오른쪽 아래 순으로 시도합니다.

이 순서로 탐색하면 위쪽 경로가 아래쪽 경로를 최대한 막지 않게 되어 그리디하게 최대 개수를 얻을 수 있습니다. 탐색 중 마지막 열에 도달하면 성공이고, 어느 방향으로도 진행할 수 없으면 실패입니다.

실패한 경우에도 방문 표시는 그대로 유지합니다. 어차피 그 칸을 통해서는 마지막 열까지 도달할 수 없다는 것이 확인되었기 때문입니다.

---

Code

C#

using System;

class Program {
  static int R, C, answer;
  static char[][] grid = Array.Empty<char[]>();
  static bool[][] visited = Array.Empty<bool[]>();
  static readonly (int dy, int dx)[] dir = { (-1, 1), (0, 1), (1, 1) };

  static bool Dfs(int y, int x) {
    visited[y][x] = true;
    if (x == C - 1) return true;

    foreach (var (dy, dx) in dir) {
      var ny = y + dy;
      var nx = x + dx;
      if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
      if (visited[ny][nx] || grid[ny][nx] == 'x') continue;
      if (Dfs(ny, nx)) return true;
    }
    return false;
  }

  static void Main() {
    var first = Console.ReadLine()!.Split();
    R = int.Parse(first[0]);
    C = int.Parse(first[1]);
    grid = new char[R][];
    visited = new bool[R][];
    for (var i = 0; i < R; i++) {
      grid[i] = Console.ReadLine()!.ToCharArray();
      visited[i] = new bool[C];
    }

    for (var i = 0; i < R; i++)
      if (Dfs(i, 0)) answer++;

    Console.WriteLine(answer);
  }
}

C++

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

typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;

int R, C;
vs grid;
vvb vis;
const int dy[3] = {-1, 0, 1};
const int dx[3] = {1, 1, 1};

bool dfs(int y, int x) {
  vis[y][x] = true;
  if (x == C - 1) return true;
  for (int d = 0; d < 3; d++) {
    int ny = y + dy[d], nx = x + dx[d];
    if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
    if (vis[ny][nx] || grid[ny][nx] == 'x') continue;
    if (dfs(ny, nx)) return true;
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> R >> C;
  grid.resize(R);
  for (auto &row : grid) cin >> row;
  vis.assign(R, vb(C, false));

  int ans = 0;
  for (int i = 0; i < R; i++)
    if (dfs(i, 0)) ans++;

  cout << ans << "\n";

  return 0;
}