구름톤 챌린지 3주차 학습 일기(2) 맞왜틀?

서론

DFS로 풀다가 Runtime Error...

BFS로 풀다가 Timeout....

으악 살려줘~

3주 2일차

2일 차 발전기

문제 : 상하좌우로 "연결된 집" 집단의 개수를 구하여라

 

문제 설명을 비약적으로 짧게 만들었으나 문제를 푸는 데에 문제는 없다...

처음엔 DFS를 통해서 풀었으나 1000 * 1000과 같은 경우에 Runtime Error(재귀 한도 초과로 추측)가 발생하여 BFS로 짜주었다.

 

오늘도 맞왜틀? Timeout을 중점으로 글을 쓴다.

◆코드 전문◆

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

int N, answer = 0;
int map[1100][1100];
int dx[4]{1, -1, 0, 0};
int dy[4]{0, 0, 1, -1};
queue<pair<int, int>> que;

void bfs(int y, int x)
{
    que.push({y, x});
    while (!que.empty())
    {
        y = que.front().first;
        x = que.front().second;
        que.pop();
        
        //수정 전
        //map[y][x] = 0;

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N)
            {
                if (map[ny][nx] == 1)
                {
                    que.push({ny, nx});
                    //수정 후
                    map[ny][nx] = 0;
                }
            }
        }
    }
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> map[i][j];
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] == 1)
            {
                bfs(i, j);
                answer++;
            }
        }
    }
    cout << answer;
}

간단한 코드 설명을 하자면, 입력을 받고 반복문을 통해 1을 가진 map의 위치를 bfs함수에 넘긴다. 그리고 answer을 하나 증가시킨다.(집이 이어져 있지 않다면 bfs가 끝나고, 반복문 안에서 안 이어진 집의 위치로 bfs 하게 된다.)

이후 queue를 통해서 좌표의 상하좌우 값이 1이라면 이를 queue에 넣고 map의 좌표는 0으로 만든다.

queue가 빌때까지 반복하며 모든 map이 0이라면, 답을 출력한다.

 

맞왜틀? (Timeout)(어려웠던 점)

DFS는 재귀 호출이 1000 * 1000 = 1000000(백만) 일어날 수 있는 TC가 있어서 실패함을 느끼고 BFS로 구현하였다.

하지만 Timeout이 발생하였고, 이에 대해 설명하겠다.

 

문제는 BFS 로직 안에서 발생하였다.

void bfs(int y, int x)
{
    que.push({y, x});
    while (!que.empty())
    {
        y = que.front().first;
        x = que.front().second;
        que.pop();
        
        //수정 전
        //map[y][x] = 0;

        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N)
            {
                if (map[ny][nx] == 1)
                {
                    que.push({ny, nx});
                    //수정 후
                    map[ny][nx] = 0;
                }
            }
        }
    }
}

수정 전에서는 반복문 처음에 map[y][x] = 0을 해주었는데 이 경우, 큐에서 push할 때 map을 바꿔 줌으로 queue에 같은 값이 많이 들어간다.

아래 사진을 보도록 하자. (형광 팬은 queue에 넣는 위치를 뜻한다.)

진행과정

중간부터 bfs 진행을 하게 될 때 처음은 상관없지만 while문이 2번째 도는 부분에서 같은 위치가 queue에 두 번 들어가는 것을 볼 수 있다. (1?, 형광펜 중복 색칠)

지금 눈에 보이는 건 고작 4개이지만, 값이 커질수록 점점 늘어나서 Timeout을 발생시키는 것이다.

이를 막기 위해 queue에 넣으면 서 0으로 만들어 주는 map[ny][nx] = 0; 로 코드를 수정하여 문제를 해결하였다.

배운 점

전에 BFS 문제를 풀 때도 겪었던 문제이다. 그래서 더욱 빠르게 찾을 순 있었지만, 평상시에 예방해야 되고 기본적인 알고리즘인 만큼 외워야겠다.

DFS는 보통 1만 번이 넘으면 안 된다는 사실을 이번 문제를 통해서 알게 되었다.

항상 최선의 경우 DFS를 사용하려는 버릇을 없애야겠다.

(queue를 따로 선언하지 않아도 되는 편안함 때문이기도 하지만...)

 

느낀 점

맞왜틀?을 자주 겪으면서 인내심이 점점 올라감을 느낄 수 있었다.

학교에서 알고리즘 시간에 실습은 하지 않고 이론만 수업하였기 때문에 구현 부분에 있어서 많이 취약함을 느꼈다.

자주 구현해서 오류 없이 빠르게 구현을 하는 실력을 기르도록 하자.