글 읽기 - DFS로 풀면 안 되는 문제인가요?

fanfolderkim 5년 전 0

다른 분들 질문을 보니 다들 BFS로 푸셨는데,

DFS로 열심히 풀고 다른 곳에서 테스트할 때는 잘 되는데

채점을 돌려보면 바로 시간초과가 뜨더군요. 풀이의 잘못인지

코드 로직의 잘못인지 헷갈리네요.

#include <iostream>
#include <cstring>
using namespace std;

int N, M;
int map[1000][1000];
bool visited[1000][1000];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
int days = 0;
bool stuck = false, keepgoing = false;

void inputMap(), DFS(), Solution();
bool carryOn(), isInside(int, int);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    inputMap();
    
    if (!carryOn()) { // 프로그램을 한 번이라도 실행할 필요가 있는가?
        cout << "0";
    }
    // 사방이 막힌 칸이 있는 경우
    else if (stuck)
        cout << "-1";
    // 정상적으로 프로그램을 돌리는 경우
    else {
        Solution();
        cout << days - 1;
    }
    return 0;
}

void inputMap() {
    cin >> M >> N;
    for (int y = 0; y < N; y++)
        for (int x = 0; x < M; x++)
            cin >> map[y][x];
}

void DFS(int y, int x) {
    visited[y][x] = true;
    if (map[y][x] == 0)
        map[y][x] = 1;
    int dy, dx;
    for (int i = 0; i < 4; i++) {
        dx = x + dir[i][0];
        dy = y + dir[i][1];
        
        if (isInside(dy, dx) && map[dy][dx] == 0) {
            visited[dy][dx] = true;
            map[dy][dx] = 1;
        }
    }
}

bool carryOn() { // 더 진행할 필요가 있는가?
    int dy, dx;
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            if (map[y][x] != -1) {
                int stuckCnt = 0;
                for (int i = 0; i < 4; i++) {
                    dx = x + dir[i][0];
                    dy = y + dir[i][1];
                    if (!isInside(dy, dx) || map[dy][dx] == -1)
                        stuckCnt++;
                }
                if (stuckCnt == 4)
                    stuck = true;
            }
            if (map[y][x] == 0) // 안 익은 토마토가 있는가?
                keepgoing = true; // 진행하라
        }
    }
    return keepgoing;
}

void Solution() {
    int y, x;
    while (keepgoing) {
        keepgoing = false;
        for (y = 0; y < N; y++) {
            for (x = 0; x < M; x++) {
                if (map[y][x] == 1 && !visited[y][x])
                    DFS(y, x);
                else if (map[y][x] == 0 && !visited[y][x]) {
                    keepgoing = true;
                    visited[y][x] = true;
                }
                if (days == 0 && stuck) {
                    days = -1;
                    return;
                }
            }
        }
        for (int i = 0; i < N; i++)
            memset(visited[i], 0, sizeof(int) * M);
        days++;
    }
}

bool isInside(int y, int x) {
    return (x >=0 && x < M) && (y >= 0 && y < N);
}

djm03178 5년 전 1

우선 근본적인 것부터 말씀드리자면, 이 코드는 DFS가 아닙니다. DFS라고 하려면, 특정 지점에서 시작한 뒤에 더 이상 이동이 불가능할 때까지 끝까지 들어갔다 나와야 하는데 이 코드에서는 그냥 시작 지점에 인접한 칸들에 1을 체크해두는 것이 끝입니다. 이 문제는 DFS로 풀 수 있는 문제도 아니고, 코드 자체도 DFS가 아니라 BFS에 가깝습니다. 정해도 BFS입니다.

코드가 시간 초과가 나는 이유는 하루 하루가 지날 때마다 전체 맵을 전부 순회하면서 토마토를 찾아야 하기 때문인데, 그럴 필요가 없습니다. 바로 지난 날에 새로 익은 토마토가 어디 있는지에 대한 목록만 가지고 있으면, 그 지점들로부터만 다시 한 칸씩 들어가면 되니까요. 이를 위해 queue를 사용하는 것이고, 이렇게 하는 게 BFS의 기본입니다.

visited 배열도 마찬가지로 이전에 방문했던 기록을 매일 초기화할 필요가 없습니다. 새로 익은 토마토들로부터만 탐색을 한다면, 이전까지 방문했던 칸에 다시 도달할 일이 없으니까요.

fanfolderkim 5년 전 0

DFS로 풀면 안 되는 것이 맞군요. 그리고 새로 익은 토마토에 대해서만 탐색을 할 생각을 못했네요. 감사합니다

댓글을 작성하려면 로그인해야 합니다.