[백준] 빵집

그리디 문제를 보고 있는데 탐색 문제가 나와서 좀 반가운 마음에 풀어보았다. 문제를 읽었는데 진짜 무슨 소리인지 감을 못잡겠어서 예시를 보고도 솔직히 어떻게 푸는지 몰랐다. 그런데 정답 코드가 적혀있는 블로그를 보면서 풀이에 대한 해석만 보고 문제는 나 혼자 풀어야겠다 싶었는데 풀이 자체는 쉬웠는데 아이디어가 어려운 문제였다.

이 문제는 파이프를 연결시켜서 첫번째 열에서 시작하고 마지막 열 어떤 부분이든 도착하면 되는 문제였다. 다만 파이프는 겹치지 않기때문에 한번 파이프를 연결시키면 그래도 끝났어야 했다. 이때, 파이프를 연결하는 방향은 오른쪽, 오른쪽 대각선 위, 아랙 총 3가지가 있는데 이 순서를 생각하는게 이 문제의 핵심이었다.

최대한 많은 파이프를 연결해주기 위해서 그리디 하게 생각해야 했던 부분은 가장 위쪽에 파이프라인 부터 채워주고 나머지를 채워야지 가장 많은 파이프를 만들 수 있었다. 왜냐하면 이미 지나간 파이프라인은 겹치지 못하기 때문에 최대한의 파이프를 만들기 위해서는 가장 윗쪽부터 채웠어야 하기 때문이다.

그럼으로 방향은 대각선 위, 오른쪽, 대각선 아래 순으로 해야지 문제를 통과할 수 있었다. 이 순서중 하나라도 어긋나면은 최대 파이프라인을 못만들었다. 정말 신박하다고 생각했고 이런 아이디어를 만드는게 그리디 문제의 핵심같다. 더 노력해야겠다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, M; 
char matrix[10001][10001]; 
bool visited[10001][10001]; 
int answer = 0;
bool flag = false;  
vector<pair<int,int>> dir = {{-1,1},{0,1},{1,1}}; 

void Input(){
    cin >> N >> M; 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> matrix[i][j]; 
        }
    }
}

void dfs(int x, int y){
    if(x < 0 || x >= N || y < 0 || y >= M || matrix[x][y] == 'x' || visited[x][y] || flag) return; 
    visited[x][y] = true; 
    if(y == M-1){
        //cout << x << ' ' << y << endl; 
        answer++; 
        flag = true; 
        return; 
    }
    dfs(x-1,y+1);
    dfs(x,y+1); 
    dfs(x+1,y+1); 
}

void Solution(){
    for(int i = 0; i < N; i++){
        flag = false; 
        dfs(i,0); 
    }
    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

배운점:
1. 그리디한 DFS
2. DFS 탐색 종료 시점은 flag 로 컨트롤 할 수 있다.