1. 단지번호붙이기

https://www.acmicpc.net/problem/2667

구현

• DFS의 가장 깔끔한 정석 문제라고 생각한다.
• map에서 1인 부분을 발견하면, 그 주변의 1을 끝까지 탐색하며,
  0으로 바꿔버리고 영역의 크기를 구한다.
  모두 구하면, vector에 집어넣는다.
• vector값을 sort하고, 출력한다.

문제점

• 없

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool map[26][26];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int N;
int result=0;
vector<int> danji;

void DFS(int x, int y)
{
    // 0이면 return
    if (!map[x][y])
    {
        return;
    }

    // 1이면 result에 추가, 다시 방문 못하게 0으로 전환
    if (map[x][y])
    {
        result++;
        map[x][y] = 0;
    }

    // 현재에서 4방향을 DFS에 넣음
    for (int i = 0; i < 4; i++)
    {
        int cx = x + dx[i];
        int cy = y + dy[i];

        if (cx < 0 || N < cx || cy < 0 || N < cy)
        {
            continue;
        }
        else
        {
            DFS(cx, cy);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    // 입력
    for (int i = 0; i < N; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < N; j++)
        {
            map[i][j] = s[j] - '0';
        }
    }

    // map[i][j]가 1이면 DFS넣음
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j])  // 1이어야만 danji에 값을 넣음
            {
                DFS(i, j);
                danji.push_back(result);
                result = 0;
            }
        }
    }

    // 정렬해야함
    sort(danji.begin(), danji.end());

    // 출력
    cout << danji.size() << "\n";
    for (int i = 0; i < danji.size(); i++)
    {
        cout << danji[i] << "\n";
    }
    return 0;
}

2. 유기농 배추

https://www.acmicpc.net/problem/1012

구현

• DFS하는게 편하긴 하지만, BFS로 풀었다.
• BFS는 어떻게든 queue를 사용한다.

문제점
1. 이 문제가 M N 순서대로 가로 세로를 의미해서 헷갈렸다.
2. 아래 코드에서 if문과 0으로 만드는 코드를 제외해도
cx,cy는 어쨌든 while문의 처음에 의해 1인지 0인지 판별하게 되는데,
그래도 if문을 적어야하는 이유는, 중복계산을 상당히 방지할 수 있기 때문.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int T, K;
int N, M;

bool map[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int worm = 0;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;

    while(T--)
    {
        // 가로, 세로, 배추개수
        cin >> M >> N >> K;
        
        // 초기화
        worm = 0;
        memset(map, 0, sizeof(map));
        queue<pair<int, int>> q;

        // 배추심기
        while(K--)
        {
            int x, y;
            cin >> y >> x;
            map[x][y] = 1;
        }

        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                if(!map[i][j])
                {
                    continue;
                }

                if(map[i][j])
                {
                    worm++;
                    q.push({i, j});
                    map[i][j] = 0;
                }

                while(!q.empty())
                {
                    int x = q.front().first;
                    int y = q.front().second;

                    q.pop();

                    for(int k=0;k<4;k++)
                    {
                        int cx = x + dx[k];
                        int cy = y + dy[k];

                        if(cx < 0 || cx >= N || cy < 0 || cy >= M)
                        {
                            continue;
                        }
                        else
                        {
                            if(map[cx][cy])
                            {
                                map[cx][cy] = 0;
                                q.push({cx, cy});
                            }
                        }
                    }
                }
            }
        }
        cout << worm << "\n";
    }

    return 0;   
}

DFS와 BFS차이는 크게 없다.
DFS는 큐에 넣지 않는 것이고,
BFS는 큐에 넣는 것이다.
따라서 DFS는 주어진 일을 바로바로 수행하지만,
BFS는 대기열에 넣어두고 순서가 되면 수행한다.

3. A-B-C-D-E 친구

https://www.acmicpc.net/problem/13023

구현

• 구현은 어렵지 않았다.
• 하지만 벡터를 사용해야만 풀린다.
  N이 2000개라서, 2000개를 도는 DFS를 해야만 했는데,
  시간초과가 났다.
  따라서 벡터로 구현
• 백트래킹을 사용해야 했다.

문제점
1. DFS 백트래킹을 해야했다.
그래야만 아닌 경로에서 다시 빠져나와 값을 찾을 수 있다.
https://www.acmicpc.net/board/view/98422
2. 그냥 벡터를 사용해야만 한다.
그냥 int대신 long long을 사용하는것처럼...

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

int N, M;
vector<int> v[2001];    // 벡터를 써야만 한다.
bool visited[2001];

int flag = 0;

void DFS(int num, int count)
{
    if (count == 4)
    {
        flag = 1;
        return;
    }

    for (auto i : v[num])
    {
        if (!visited[i])
        {
            visited[i] = true;
            DFS(i, count + 1);
            visited[i] = false; // 백트래킹
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        int from, to;
        cin >> from >> to;

        v[from].push_back(to);
        v[to].push_back(from);
    }

    // v[i]는 i번째 수에 연결된 원소들은 v[i][0]부터 차곡차곡 저장
    for (int i = 0; i < N; i++)
    {
        for (auto j : v[i])
        {
            if (flag)
            {
                cout << flag;
                return 0;
            }

            memset(visited, 0, sizeof(visited));
            visited[i] = visited[j] = true;

            DFS(j, 1);
        }
    }
    cout << flag;

    return 0;
}

4. 연결요소의 개수

https://www.acmicpc.net/problem/11724

구현

• 노드가 주어지고, 연결이 주어진다.
• 연결된 노드는 하나의 섬으로 치고,
  연결이 하나도 안 된 노드도 하나의 섬으로 친다.
  섬의 개수를 구하면 되는 문제.
• 연결이 있는 노드에 한해, DFS를 돌리며 visited체크를 하며 방문하지 못하게 막는다.
• 연결이 없는 노드는 그 자체로 섬이므로 결과값을 증가.

문제점
1. 연결이 없는 경우, 연결이 단 1개인 경우
이런 당연한 경우들을 반례로써 바로 생각하지 못했다.
5 0 이런거나 5 1 / 2 3 = 4 이런것들..

#include <iostream>
#include <vector>

using namespace std;

int N, M;
int result = 0;
vector<int> v[1001];
bool visited[1001];

// 간단한 DFS, 백트래킹하지 않는 이유는, 어떻게든 연결이 되어있어서
// visited를 모두 순회할 수 있기 때문, 그리고 if-return문도 딱히 없다.
void DFS(int n)
{
    for(auto j : v[n])
    {
        if(!visited[j])
        {
            visited[j] = 1;
            DFS(j);
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    // 입력 (양방향)
    for(int i=0;i<M;i++)
    {
        int from, to;
        cin >> from >> to;

        v[from].push_back(to);
        v[to].push_back(from);
    }

    
    for(int i=1;i<N+1;i++)
    {
        // 연결된 것이 하나도 없는 경우 - 외딴섬
        // 굳이 visited 체크하지 않아도 된다.
        if(v[i].size()==0)
        {
            result++;
            continue;
        }

        // 연결된 것이 있는 경우, DFS돌며 visited체크
        for(auto j : v[i])
        {
            if(!visited[j])
            {
                visited[j] = 1;
                DFS(j);
                result++;
            }
        }
    }

    cout << result;

    return 0;   
}

5. 섬의 개수

구현

• 일반적인 섬의 개수이지만, 대각선도 섬으로 인정한다.
• 그것 외에는 평범한 쉬운 문제.

문제점
1. N과 M이 세로, 가로가 아니라,
가로,세로 순서로 주어지는 것이 문제였다.

• 항상 어떻게든 꼬니까 신경쓰자.

#include <iostream>
#include <cstring>

using namespace std;

int sum = 0;
int N, M;
bool map[51][51];

int dx[8]={-1,1,0,0,1,-1,1,-1};
int dy[8]={0,0,-1,1,1,-1,-1,1};

void DFS(int x, int y)
{
    map[x][y] = 0;

    for (int i = 0; i < 8; i++)
    {
        int cx = x + dx[i];
        int cy = y + dy[i];

        if (cx < 0 || cx >= N || cy < 0 || cy >= M)
        {
            continue;
        }

        if (map[cx][cy])
        {
            DFS(cx, cy);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    while (true)
    {
        sum = 0;
        memset(map, 0, sizeof(map));

        // M이 가로, N이 세로
        cin >> M >> N;
        if (N == 0 && M == 0)
        {
            return 0;
        }

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

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (map[i][j])
                {
                    DFS(i, j);
                    sum++;
                }
            }
        }

        cout << sum << "\n";
    }

    return 0;
}

6. 미로탐색

https://www.acmicpc.net/problem/2178

구현

• 그냥 00부터 n-1 m-1로 가는 경로의 최소값을 찾는 문제
• 경로값을 queue<pair<pair<int, int>,int>> q로 같이 큐에 전달.
• min으로 dp처럼 비교를 하지 않아도 되는 이유는,
  BFS라서 무조건 처음 방문하는 것이 최단거리이기 때문.

문제점
1. 메모리초과
메모리 초과가 떴을 때, string배열로 map을 선언한 것을 vector로 바꾸어 보았다.
하지만 그게 문제가 아니었다.
2. 메모리초과 2
queue에 넣기 전, visited 체크를 해야만 한다.
그래야지 다른 큐에서 해당 큐를 방문할 필요가 없다는 것을 알리고
무의미한 중복을 방지할 수가 있다.
조심하자.

#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

int N, M;
int sum=0;
//string map[100];
vector<string> map;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    for(int i=0; i<N; i++)
    {   
        string s;
        cin >> s;
        map.push_back(s);
    }    

    queue<pair<pair<int, int>,int>> q;
    q.push({{0,0},1});

    while(!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int count = q.front().second;
        map[x][y] = '0';
        q.pop();

        if(x==N-1 && y==M-1)
        {
            cout << count;
            return 0;
        }

        for(int i=0;i<4;i++)
        {
            int cx = x + dx[i];
            int cy = y + dy[i];

            if(cx < 0 || cx >= N || cy < 0 || cy >= M)
            {
                continue;
            }

            if(map[cx][cy]=='1')
            {
                map[cx][cy] = '0';  // BFS 큐에 들어가기 전에 방문표시를 해야 함
                q.push({{cx, cy},count+1});
            }
        }

    }

    return 0;   
}

7. 토마토

https://www.acmicpc.net/problem/7576

구현

• 익은 토마토가 주변의 익지 않은 토마토를 익게 한다.
  물 범람문제와 비슷하고, 최소 걸리는 시간을 출력.
• 이전에 풀어봤는데, 2차원배열이 아닌, vector를 이용하여 구현해보았다.
  DFS의 경우, 2차원배열로 하면 [2000][2000]방문은 시간초과가 난다.
  사실 미리 크기가 고정된 2차원 배열 토마토 맵 같은 경우는
  Vector를 사용하는게 의미가 없다.
  어떤 연결이나 간선 이런거에나 의미가 있음.
  (한 노드에 연결된 개수가 서로 다른 경우)
• 추가로, queue의 구조에 day값을 넣도록 하여,
  따로 int형 2차원 배열을 만들어서 day값을 저장해두지 않도록 했다.
  현재 문제에선 최종 값만 중요하기 때문이다.

문제점

• queue에 한 노드를 넣자마자 while문을 돌린다면, BFS가 아니라 DFS가 된다.
• 헷갈릴까봐 다시 적지만, DFS로 최단거리를 비교하려면,
  모든 DFS 경로를 탐색 후 생긴 각각의 결과값 중 최소값을
  찾아내야만 한다.
  BFS는 그냥 가장 먼저 도착하는게 최단거리.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M;
queue<pair<pair<int, int>,int>> q;

// 왠만해선 vector로 map 구현할 것 (시간초과)
vector<int> map[1001];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};

int result = 0;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> M >> N;

    // 입력
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            int n;
            cin >> n;
            map[i].push_back(n);
        }
    }

    // 1 queue에 시작점들 넣음
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            if(map[i][j]==1)
            {
                q.push({{i,j},0});
            }
        }
    }

    // 2 BFS - 각 시작점으로부터 동시에 퍼짐
    while(!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int day = q.front().second;

        q.pop();

        result = max(result, day);

         for(int i=0;i<4;i++)
        {
            int cx = x + dx[i];
            int cy = y + dy[i];

            if(cx < 0 || cx >= N || cy < 0 || cy >= M)
            {
                continue;
            }

            if(map[cx][cy]==0)
            {
                map[cx][cy] = 1;
                q.push({{cx,cy}, day+1});
            }
        }
    }

    // 3 출력 - 결과에 0이 있으면 -1 출력
    for(int i=0;i<N;i++)
    {
        for(auto j : map[i])
        {
            if(j==0)
            {
                cout << -1;
                return 0;
            }
        }
    }

    // 4 출력 - 문제 없을 경우
    cout << result;

    return 0;   
}