백준 3109 빵집

원웅이의 범죄행위를 도와주어야 하는 문제이다. 

가장 왼쪽 열에서 가장 오른쪽 열까지 우상, 우, 우하로 움직이며 경로가 몇개가 되는지 구하는 문제이다.

각 경로는 서로 겹쳐서는 안된다.

 

경로를 찾을때는 DFS로 탐색을 한다.

현재 픽셀에서 우상, 우, 우하로 탐색하면서 재귀로 호출한다. - 우상, 우, 우하 탐색을 했을 때 전부 true가 없으면 false를 최종적으로 리턴하게 된다.

만약 현재 픽셀이 가장 오른쪽 열이라면, true를 리턴한다.

 

DFS를 짤 때, 재귀로 일단 생각하게 되는데 앞으로 풀어볼 때는 재귀가 아닌 코드로 한번 작성해보아야겠다. 재귀로 짤 경우 디버그가... 너무... 힘들다...

 

Visit[][] 배열은 Map 크기와 동일하게 만들어서 각 픽셀을 방문할때마다 true로 만든다.

초기 접근에서는 마지막까지 탐색해서 파이프가 완성될 경우만 true로 했었는데, 시간초과가 떴다.

다시 생각해보니 그 픽셀을 방문했고, 그 뒤로 탐색을 해서 파이프가 완성되지 않았으면, 그 픽셀은 어차피 그 뒤로 탐색 할 필요가 없었다.

그래서 일단 무조건 방문 가능한 조건이기만 하면 visit배열을 true로 만들게 하니 맞았다.

 

기본적인 탐색을 완성하면, 맵에서 가장 왼쪽 열 픽셀을 순회하며 탐색하면 된다.

---

#include <iostream>
#include <string>

struct pos
{
    int y;
    int x;
    pos(int y, int x) : y(y), x(x) {}
};

int dx[] = {1, 1 ,1};
int dy[] = {-1, 0, 1};
std::string map[10000];
bool visited[10000][500];
int H, W;

bool getPipe(pos cur)
{
    bool found = false;
    if (cur.x == W - 1)
    {   
        visited[cur.y][cur.x] = true;
        return true;
    }
    for (int i = 0; i < 3 ; i++)
    {
        int ny = cur.y + dy[i];
        int nx = cur.x + dx[i];
        if (ny < 0 || ny > H - 1 || nx < 0 || nx > W - 1 || visited[ny][nx] || map[ny][nx] == 'x')
            continue;
        visited[cur.y][cur.x] = true; // 방문 할수 있기만 하면 체크 필요 -> 파이프 놓았어도 방문 할 필요 없고, 파이프 못 놓았어도, 이후 방문 필요 없음.
        if (getPipe(pos(ny, nx)))
        {
            found = true;
            break;
        }
    }
    return found;
}

int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> H >> W;
    
    for (int i = 0 ; i < H; i++)
    {
        std::string inp;
        std::cin >> inp;
        map[i] += inp;
    }
    int pathCnt = 0;
    for (int i = 0; i < H; i++)
    {
        if (getPipe(pos(i, 0)))
            pathCnt++;
    }
    std::cout << pathCnt;
}

 

본 문제는 입출력이 많아, 입출력 속도 향상하는 코드 3줄을 main 문에 넣어야 한다. 그러고 나면 완성.

원래 전역을 잘 안쓰려고 하는 경향이 있는데, 알고리즘 문제를 풀면서 전역변수를 너무 많이 쓰는것 같다. 한 문제 문제같이 작은 코드는 괜찮은데, 이게 체화되어서 나중에 큰 프로젝트를 할 때도 써버리면 안될것 같다. 습관 들지 않게 조심할 필요가 있다.

 

오늘도 평온한 하루가 되길. 슨민.