백준 3109번 빵집

🔒[문제 url]

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

🔑알고리즘

최대한 많은 파이프를 연결하기 위해서, 윗 행부터 시작하여 파이프를 가능한 위쪽으로 Greedy하게 설치하자.
즉, 오른쪽 위 대각선 오른쪽 오른쪽 아래 대각선 순으로 말이다.

• 윗 행부터 시작하여 앞서 언급한 세 방향에 대해 DFS 탐색을 진행한다.
  이때 원웅이의 빵집까지 연결할 수 있다면, 설치한 모든 경로에 x표기한다.
  
  
• 원웅이의 빵집까지 연결할 수 없다면?
  • 이후 불필요한 탐색을 막기 위해, 해당 경로에도 x 표기를 한다.

🐾부분 코드

int r, c;
int map[10001][501];
int dir[3][2] = { {-1,1},{0,1},{1,1} }; // 오른쪽 위 대각, 오른쪽, 오른쪽 아래 대각

<변수 선언>
dir 배열의 순서에 주목하자.
Greedy하게 접근해야하므로 0번째 index부터 탐색한다.

bool DFS(int row, int col)
{
    int x = row, y = col;

    // 원웅이 빵집에 도달했다면
    if (col == c)
    {
        ans++;
        return true;
    }

    for (int i = 0; i < 3; i++)
    {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if (1 <= nx && nx <= r && 1 <= ny && ny <= c)
        {
            if (map[nx][ny] == '.' && DFS(nx, ny))
            {
                map[nx][ny] = 'x';
                return true;
            }
            // 가지치기 : 이 경로를 통해 연결할 수 없음
            else map[nx][ny] = 'x';
        }
    }
    // 원웅이 빵집에 연결할 수 없다면
    return false;
}

<DFS 함수>
원웅이의 빵집에 도달할때마다 ans를 증가시킨다.
위에서 언급한 알고리즘에 따라 x를 표기하며 탐색한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <stdio.h> // c
using namespace std;

int r, c;
int map[10001][501];
int dir[3][2] = { {-1,1},{0,1},{1,1} }; // 오른쪽 위 대각, 오른쪽, 오른쪽 아래 대각

int ans = 0;

void INPUT()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> r >> c;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            scanf("%1s", &map[i][j]);

}

bool DFS(int row, int col)
{
    int x = row, y = col;

    // 원웅이 빵집에 도달했다면
    if (col == c)
    {
        ans++;
        return true;
    }

    for (int i = 0; i < 3; i++)
    {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if (1 <= nx && nx <= r && 1 <= ny && ny <= c)
        {
            if (map[nx][ny] == '.' && DFS(nx, ny))
            {
                map[nx][ny] = 'x';
                return true;
            }
            // 가지치기 : 이 경로를 통해 연결할 수 없음
            else map[nx][ny] = 'x';
        }
    }
    // 원웅이 빵집에 연결할 수 없다면
    return false;
}

void SOLVE()
{
    for (int i = 1; i <= r; i++) DFS(i, 1);

    cout << ans;
}



int main()
{
    INPUT();

    SOLVE();

}

🥇문제 후기

이왜골2 ?