[BOJ] 3109 : PLINOVOD

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

---

문제해석

 왼쪽끝에서 오른쪽끝으로 파이프를 연결해 길을 만들고 싶은데, 파이프끼리 겹치면 안되고 파이프는 오른쪽, 오른쪽 대각선 위, 오른쪽 대각선 아래 로 이어서 설치할 수 있다. 길을 최대 몇 개 만들 수 있을까?

문제핵심

 1. 현재 지점에서 파이프를 연결해 길을 만들 때, 아래에서 시작하는 다른 길과 겹치지않으려면 제일 좋은 이동은 오른쪽 대각선 위 > 오른쪽 > 오른쪽 대각선 아래 가 된다. 우리는 그냥 길을 최대한 많이 만들면 되므로 Greedy 하게 위에서부터 길을 만들어가면 된다.

 2. 일반적인 DFS 탐색은 탐색하고 돌아오면 visited 배열을 다시 초기화해주나, 이 문제에서는 방문해서 끝에 도달하지 못한 경로는 다른 지점에서 방문해도 어차피 끝에 도달하지 못하므로 visited 배열을 다시 초기화 해줄 필요가 없고, 초기화해준다면 경로가 겹쳐서 시간초과에 직면하게 됩니다.

알고리즘

 왼쪽 위에서부터 시작해서 DFS 탐색을 진행한다. 우선 순위가 높은 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 순으로 탐색을 진행하고 끝에 도달하게 된다면 S 지점에서 끝에 도달했다고 checked 를 한다. 그 후, S 지점에서 시작하던 탐색들을 다 종료한다. 재귀적으로 탐색을 하고 돌아왔다는 사실은 그 길로는 오른쪽 끝에 도달하지 못한다는 것을 의미한다. 따라서, visited 배열을 초기화하지 않고 그대로 남겨두어 다른 경로에서 이 지점을 탐색하는 불필요한 연산을 줄여주면 시간초과를 피할 수 있다.

#include<iostream>
 
using namespace std;
 
int R, C, ans;
int dx[3] = { -1, 0, 1 }, dy[3] = { 1, 1, 1 };
bool checked[10000];
bool visited[10000][500];
char map[10000][501];
 
void DFS(int s, int x, int y) {
    if (y == C - 1) {
        ans++;
        checked[s] = 1;
        return;
    }
    
    for (int i = 0; i < 3; i++) {
        int nX = x + dx[i], nY = y + dy[i];
        if (!(0 <= nX && nX < R && 0 <= nY && nY < C)) continue;
        if (visited[nX][nY]) continue;
        if (map[nX][nY] == 'x') continue;
 
        visited[nX][nY] = 1;
        DFS(s, nX, nY);
        if (checked[s]) return;
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        cin >> map[i];
 
    for (int i = 0; i < R; i++){    
        visited[i][0] = 1;
        DFS(i, i, 0);
    }
    cout << ans << '\n';
    return 0;
}

---