1. 1325 - DFS

실버의 마지막 문제를 풀고 골드로 넘어가려고 한다.
실버 중에서 유난히 정답비율이 낮은 문제가 존재해서
실버의 마지막 문제로 선정하였다.

정답비율이 낮은 이유는 아무래도 입력값의 범위 때문일 것 같다.
범위가 굉장히 크다.
2차원 배열이 아닌, 벡터 배열로 구현해본다.

시도

Count는 정상적으로 계산이 된다.
이제 해당 Count에서 최대값의 컴퓨터들을 찾고,
오름차순으로 정렬을 해야한다.

어떻게?

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, M;
vector<int> connection[10001]; // 10000으로해도 상관없을듯
bool visited[10001] = {
    0,
};
int count[10001] = {
    0,
};

int thisIndex = 0;

void DFS(int);

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

    cin >> N >> M; // N은 컴퓨터의 개수, M은 신뢰 연결의 개수

    // 입력 받기
    int A, B;
    for (int i = 0; i < M; i++)
    {
        cin >> A >> B;
        connection[B].push_back(A); // B를 해킹하면 A도 해킹할 수 있다
    }

    for (int i = 1; i <= 10000; i++)
    {
        memset(visited, 0, sizeof(visited));
        thisIndex = i;

        if (!connection[i].empty())
        {
            DFS(i);
        }
    }

    /*
    for (int i = 0; i < N; i++)
    {
        if (0 != count[i])
        {
            cout << i << "th computer =" << count[i] << "\n";
        }
    }
    */

    // sort
    int max = 0;
    for (int i = 1; i < 10001; i++)
    {
        if (max < count[i])
        {
            max = count[i];
        }
    }
    //cout << max;

    for (int i = 1; i < 10001; i++)
    {
        if (count[i] == max)
        {
            cout << i << " ";
        }
    }
    return 0;
}

void DFS(int num)
{
    count[thisIndex]++;

    for (int i = 0; i < connection[num].size(); i++)
    {
        if (!visited[connection[num][i]])
        {
            visited[connection[num][i]] = 1;
            DFS(connection[num][i]);
        }
    }
}

위처럼 구현은 했지만,
출력초과가 떴다.

반례는 아래와 같다.

입력
3 3
1 2
2 1
1 3
    
출력
1 2 3
    
정답
3

이런 관계로,
3에서는 1과 2로 화살표를 타고 올라갈 수 있지만,
1과 2는 3을 방문하지 못하므로 최대가 될 수 없다.

근데 왜 1일때 3을 방문하지?

해결

        if (!connection[i].empty())
        {
            visited[i] = 1;
            DFS(i);
        }

visited를 깜빡했다. 추가했다.

풀이

2차원 배열로 만들필요가 없다면
무조건 vector<int> arr[N]처럼 구성하는게 의미없는 메모리를 방지할 수 있었다.

그 외에는 일반 DFS, BFS문제와 같았다.
방문할 수 있는가? 방문할 수 있으면 간다.
여기서 조건만 계속 바뀌는거지, 큰 틀은 같았다.

2. 7576 - BFS

https://www.acmicpc.net/workbook/view/1833
골드로 간다.

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

우선 BFS방식이 떠오르긴하는데,
여태까지 했던 BFS방식과는 다르게, 시작점이 여러개이다.

어떻게 구현해야할까..
이미 방문한 곳은 다른식으로 표시를 해야할까?

음...
큐에 시작점만 싸그리 넣어두고,
BFS를 돌린다면...?

될 것 같다. 구현해본다.

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

int N, M;
int map[1000][1000];
int wall = 0;
int maxDay = 0;

queue<pair<int, int>> nextNode;

int dx[4] = {0, -1, 0, 1}; // 위왼아오
int dy[4] = {1, 0, -1, 0};

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

    cin >> M >> N; // M이 가로, N이 세로 (2~1000)
    memset(map, 0, sizeof(map));

    // map 생성 및 익은토마토 큐에 추가
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 1)
            {
                nextNode.push(make_pair(j, i));
                //cout << " tomato  x:" << i << " y" << j;
            }
            else if (map[i][j] == -1)
            {
                wall++;
            }
        }
    }

    // 익은 토마토의 개수와 모든 토마토의 개수(전체칸에서 wall만 뺀 토마토의 개수)
    // 가 같다면, 모든 토마토가 익어있는 상태라서 0 출력
    if (nextNode.size() == (N * M - wall))
    {
        cout << 0;
        return 0;
    }

    // BFS
    while (!nextNode.empty())
    {
        int x = nextNode.front().first;
        int y = nextNode.front().second;
        nextNode.pop();

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

            if(cx < 0 || cx >= M || cy < 0 || cy >= N)
            {
                continue;
            }
            else
            {
                if(map[cy][cx] == 0)
                {
                    map[cy][cx] = map[y][x] + 1;    //이전날짜의 값+1을 부여
                    maxDay = map[cy][cx];
                    nextNode.push(make_pair(cx, cy));
                }
            }
        }
    }

    // 다 하고서도 익지 않은 토마토가 있다면, -1을 출력
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (map[i][j] == 0)
            {
                cout << -1;
                return 0;
            }
        }
    }

    cout << maxDay -1; //시간이므로 -1일

    return 0;
}

음... 안된다.

해결

가로, 세로가 들어가야하는데
실수가 있었다. 바로 해결.

풀이

여러곳이 시작지점이라면,
여러곳을 Queue에 넣는다.

시작점이 여러곳인 이런 문제는
DFS로는 구현하기 까다로울 것 같다.

3. 1987 - DFS / 백트래킹

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

이번에는 문자로 된 맵이다.
시작점도 고정되어있고, 단순히 최대칸수를 구하는 문제이다.
간단해보인다. 구현해본다.

시도

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

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

int count = 1;

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

    int N, M;
    cin >> N >> M; // N이세로 M이가로

    bool alphabet[26] = {0,};

    string s[N];
    for (int i = 0; i < N; i++)
    {
        cin >> s[i];
    }

    // A아스키 = 65 / 총 26개의 알파벳

    queue<pair<int, int>> nextNode;
    nextNode.push(make_pair(0, 0));
    alphabet[s[0][0] - 65] = 1;

    cout << "x:" << 0 << " y:" << 0 << "\n";
    while (!nextNode.empty())
    {
        int x = nextNode.front().first;
        int y = nextNode.front().second;
        nextNode.pop();

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

            if(cx < 0 || cx >= M || cy < 0 || cy >= N)
            {
                continue;
            }
            else
            {
                if(alphabet[s[cy][cx]-65] == 0) //한번도 나오지 않은 알파벳이라면
                {
                    cout << "x:" << cx << " y:" << cy << "\n";
                    count++;
                    alphabet[s[cy][cx]-65] = 1;
                    nextNode.push(make_pair(cx, cy));
                }
            }
        }
    }
    cout << count;

    return 0;
}

위의 코드로는 최단거리만 구하게 된다.
DFS의 백트래킹을 사용해야될 듯 하다.

시도 2

어떤 문장도 출력이 되지 않는다..

왜?

무한루프를 도나?

seg fault였다.

해결

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

int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
bool alphabet[26] = {
    0,
};
string s[20] = {
    "",
};

int N, M;
int maxCount = 0;

void DFS(int, int, int);

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

    cin >> N >> M; // N이세로 M이가로

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

    // A아스키 = 65 / 총 26개의 알파벳
    alphabet[s[0][0] - 65] = 1;
    DFS(0, 0, 1);
    
    cout << maxCount;
    
    return 0;
}

void DFS(int x, int y, int count)
{
    bool exitFlag = false;

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

        if (cx < 0 || cx >= M || cy < 0 || cy >= N)
        {
            continue;
        }
        else
        {
            // 방문하지 않았다면
            if (!alphabet[s[cy][cx]-65])
            {
                exitFlag = true; //중요

                alphabet[s[cy][cx]-65] = 1;
                DFS(cx, cy, count+1);
                alphabet[s[cy][cx]-65] = 0;
            }
        }
    }
    // 더이상 갈곳이 없는 막다른길
    // 해당 경우의 수의 마지막 경로이므로 답을 받아온다
    if(exitFlag==false)
    {
        if(maxCount < count)
        {
            maxCount = count;
        }
        return;
    }
}

풀이

단순히 한 점에서 최대한 끝까지 가는 것이 아니라,
더 좋은 "경우의 수"를 찾기 위해서 경우의 수를 따져봐야하는 문제였고,

이를 위해선 갔던길도 혹시나하고 돌아가는 백트래킹이 필요했고,
구현하기 위해선 DFS를 사용해야만 했다.
(BFS로 백트래킹하는건 난해하다)

백트래킹을 사용하는것은 간단했는데, 아래 2가지 요소만 추가되면 된다.

• 기존의 문제처럼 DFS의 전에는 똑같이 visited를 true로 만들고,
  DFS이후 visited를 false로 만들어야한다.

• 그리고 갈길이 없으면 return하도록 종료조건도 만들어야한다.

백트래킹이 어려운건 아니었는데, 막상 구현하려니 헷갈렸다.

4. 1600 - BFS

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

난이도가 상당히 높아보인다.

백트래킹을 하긴하는데, 체스의 말 기물과 같은 능력을 사용할지도 정해야한다.

음...

가능할까?

우선 경로없이 최단거리를 찾는 문제이기 때문에
BFS가 훨씬 유리해보인다.

하지만 언제 말을 사용해야할까?
장애물을 뛰어넘을 때까지 아껴야할것 같긴한데..

시도

일단 생각한대로 구현해봤는데, 이상하다.

맨 오른쪽 5에서 갈 곳이 아래에 있는데 가질 않았다.
맨 왼쪽 5에서도 아래로 가지 않았다..

왜?

#include <iostream>
#include <queue>

#include <cstring>
using namespace std;

int dx[4] = {1, 0, -1, 0}; // 오아왼위
int dy[4] = {0, -1, 0, 1};

int hx[8] = {2, 1, -1, -2, -2, -1, 1, 2}; // 오아 왼아 왼위 오위
int hy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

int K;    // 능력 사용 개수
int N, M; // 가로 N, 세로 M
int map[200][200];

void printmap();

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

    cin >> K;
    cin >> N >> M;

    memset(map, 0, sizeof(map));

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

    queue<pair<int, int>> q;

    map[0][0] = 1;
    q.push(make_pair(0, 0));

    while (!q.empty())
    {
        int canGo = false;

        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        // 마지막 점에 도달했다면 stop
        if (x == N - 1 && y == M - 1)
        {
            cout << "Succeeded";
            break;
        }

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

            if (cx < 0 || cx >= M || cy < 0 || cy >= N)
            {
                continue;
            }
            else
            {
                if (map[cy][cx] == 0)
                {
                    canGo = true;

                    map[cy][cx] = map[y][x] + 1;
                    q.push(make_pair(cx, cy));
                }
            }
        }
        
        if (!canGo)
        {
            for (int i = 0; i < 8; i++)
            {
                if (K > 0)
                {
                    int cx = x + hx[i];
                    int cy = y + hy[i];
                    if (cx < 0 || cx >= M || cy < 0 || cy >= N)
                    {
                        continue;
                    }
                    else
                    {
                        if (map[cy][cx] == 0)
                        {
                            K--;
                            canGo = true;
                            map[cy][cx] = map[y][x] + 1;
                            q.push(make_pair(cx, cy));
                        }
                    }
                }
            }

            if (!canGo)
            {
                cout << -1;
                printmap();
                return 0;
            }
        }
    }

    printmap();
    int count = map[M - 1][N - 1];
    for (int i = 0; i < K; i++)
    {
        count - 3;
    }
    cout << count;
    return 0;
}

void printmap()
{
    cout << "\n\n[print map]";
    for (int i = 0; i < M; i++)
    {
        cout << "\n";
        for (int j = 0; j < N; j++)
        {
            cout << map[i][j] << " ";
        }
    }
}

CanGo라는 변수가 잘못 동작하는 것으로 보인다.
원래 목적은, 4방향으로 모두 못가면,
말 점프를 사용하도록 하는 것이었는데,
안된다.

음..

3으로 결과가 나와야하는데도 -1로 나온다... 흠..

왜?

시도 2

https://www.acmicpc.net/board/view/103639
해당 글을 참고하였다.

코드가 간결하고,
변수명이나 구현법에 배울점이 있어서 따라해본다.

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

int K, map_x, map_y;
int dx[12] = {-1, -2, -2, -1, 1, 2, 2, 1, 0, -1, 0, 1}; // 실제론 y값
int dy[12] = {2, 1, -1, -2, -2, -1, 1, 2, 1, 0, -1, 0};
bool visit[200][200][31];
int map[200][200];

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

    memset(visit, false, sizeof(visit));
    memset(map, 0, sizeof(map));

    cin >> K;
    cin >> map_y >> map_x; // 가로와 세로 순으로 입력을 받지만, 변수명은 다르게 한다.

    for (int i = 0; i < map_x; i++) // 사실상 세로 가로로 저장이지만, 변수명이 x,y
    {
        for (int j = 0; j < map_y; j++)
        {
            cin >> map[i][j];

            // 벽을 왜 방문표시 하는거지?
            if (map[i][j] == 1)
            {
                visit[i][j][K] = true;
            }
        }
    }

    visit[0][0][K] = true;
    queue<pair<pair<int, int>, pair<int, int>>> q;
    q.push({{0, 0}, {0, K}}); // make_pair을 굳이 사용하지 않아도 됨

    while (!q.empty())
    {
        int this_x = q.front().first.first;
        int this_y = q.front().first.second;

        int moveCount = q.front().second.first;
        int horseRemain = q.front().second.second;

        q.pop();

        cout << "*******************\n";
        cout << "X " << this_x << "!\n";
        cout << "Y " << this_y << "!\n";
        cout << "moveCount = " << moveCount << "!\n";
        cout << "horseRemain = " << horseRemain << "!\n";

        // 목표에 도달 - 종료조건
        if (this_x == map_x - 1 && this_y == map_y - 1)
        {
            cout << moveCount;
            return 0;
        }

        // 상하좌우
        for (int i = 8; i < 12; i++)
        {
            int cx = this_x + dx[i];
            int cy = this_y + dy[i];

            if (cx < 0 || cx >= map_x || cy < 0 || cy >= map_y)
            {
                continue;
            }
            else
            {
                if (visit[cx][cy][horseRemain] == false)
                {
                    visit[cx][cy][horseRemain] = true;
                    q.push({{cx, cy}, {moveCount + 1, horseRemain}});
                }
            }
        }

        // horseRemain이 없다면 굳이 아래의 코드들은 실행할 필요가 없으므로
        if (horseRemain == 0)
        {
            break;
        }

        // 말 이동 8방향
        for (int i = 0; i < 8; i++)
        {
            int cx = this_x + dx[i];
            int cy = this_y + dy[i];

            if (cx < 0 || cx >= map_x || cy < 0 || cy >= map_y)
            {
                continue;
            }
            else
            {
                // horseReamin을 하나 사용한 곳을 추가할지 결정
                if (visit[cx][cy][horseRemain - 1] == false)
                {
                    visit[cx][cy][horseRemain - 1] = true;
                    q.push({{cx, cy}, {moveCount + 1, horseRemain - 1}});
                }
            }
        }
    }

    cout << "while out";

    if(q.empty())
    {
        cout << -1;
    }

    

    return 0;
}

음... queue가 비지 않았는데도 자꾸 while문을 나온다.

종료조건도 아니어서 return도 되지 않았고,
-1이 출력이 되지않았는데 어떻게?

여기가 문제였다.

해결

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

int K, map_x, map_y;
int dx[12] = {-1, -2, -2, -1, 1, 2, 2, 1, 0, -1, 0, 1}; // 실제론 y값
int dy[12] = {2, 1, -1, -2, -2, -1, 1, 2, 1, 0, -1, 0};
bool visit[200][200][31];
int map[200][200];

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

    memset(visit, false, sizeof(visit));
    memset(map, 0, sizeof(map));

    cin >> K;
    cin >> map_y >> map_x; // 가로와 세로 순으로 입력을 받지만, 변수명은 다르게 한다.

    for (int i = 0; i < map_x; i++) // 사실상 세로 가로로 저장이지만, 변수명이 x,y
    {
        for (int j = 0; j < map_y; j++)
        {
            cin >> map[i][j];

            // 벽을 왜 방문표시 하는거지?
            if (map[i][j] == 1)
            {
                visit[i][j][K] = true;
            }
        }
    }

    visit[0][0][K] = true;
    queue<pair<pair<int, int>, pair<int, int>>> q;
    q.push({{0, 0}, {0, K}}); // make_pair을 굳이 사용하지 않아도 됨

    while (!q.empty())
    {
        int this_x = q.front().first.first;
        int this_y = q.front().first.second;

        int moveCount = q.front().second.first;
        int horseRemain = q.front().second.second;

        q.pop();

        /*
        cout << "*******************\n";
        cout << "X " << this_x << "!\n";
        cout << "Y " << this_y << "!\n";
        cout << "moveCount = " << moveCount << "!\n";
        cout << "horseRemain = " << horseRemain << "!\n";
        */
       
        // 목표에 도달 - 종료조건
        if (this_x == map_x - 1 && this_y == map_y - 1)
        {
            cout << moveCount;
            return 0;
        }

        // 상하좌우
        for (int i = 8; i < 12; i++)
        {
            int cx = this_x + dx[i];
            int cy = this_y + dy[i];

            if (cx < 0 || cx >= map_x || cy < 0 || cy >= map_y)
            {
                continue;
            }
            else
            {
                if (!map[cx][cy] && visit[cx][cy][horseRemain] == false)
                {
                    visit[cx][cy][horseRemain] = true;
                    q.push({{cx, cy}, {moveCount + 1, horseRemain}});
                }
            }
        }

        // horseRemain이 없다면 굳이 아래의 코드들은 실행할 필요가 없으므로
        if (horseRemain == 0)
        {
            continue;
        }

        // 말 이동 8방향
        for (int i = 0; i < 8; i++)
        {
            int cx = this_x + dx[i];
            int cy = this_y + dy[i];

            if (cx < 0 || cx >= map_x || cy < 0 || cy >= map_y)
            {
                continue;
            }
            else
            {
                // horseReamin을 하나 사용한 곳을 추가할지 결정
                if (!map[cx][cy] && visit[cx][cy][horseRemain - 1] == false)
                {
                    visit[cx][cy][horseRemain - 1] = true;
                    q.push({{cx, cy}, {moveCount + 1, horseRemain - 1}});
                }
            }
        }
    }

    //cout << "while out";


    cout << -1;


    

    return 0;
}

풀이

구현을 어떻게 할까 고민을 많이 했던 문제였다.

4방향으로 이동이 안되면, 말의 능력을 사용해서 점프하도록 하려고 했는데,
이 생각은 틀렸다.

그 이유는, 그냥 4방향이든 말방향이든 갈 수 있으면 가고,
적절하게 방문체크만 해두면, 결과적으로 최종 도착지에 도달하는 최단거리가
BFS를 통해 구해지게 된다.

말의 능력을 언제 사용할지가 중요한 문제가 아니었다.

여기서 하나 색다른 개념이 사용되었는데,

visited를 체크하는 곳은 3차원 배열로,
말 능력의 개수에 따라 다르게 체크하게 된다.

그래서 같은 좌표의 칸이더라도,
말 능력을 1개 썼을 때, 그리고 2개 썼을 때,
같은 좌표의 땅을 밟을 수 있게 된다.
따라서 해당 칸에서 말의 능력을 사용할지 안할지까지 다룰 수 있게 된다.

BFS의 큐에 모든 정보를 넣어서 전달하면,
문제가 풀리게 된다.

코드를 보고 배운점도 존재한다.

• 1. 입력받은 x, y좌표 사용하는 법
     

map_x와 map_y라는 변수에 각각 입력의 세로줄값, 가로값을 담는다.
그 이유는, 배열은 세로-가로 순이기 떄문에, 반대로 담아야하기 때문인데,
이게 한번 반대로 담으면 queue까지 반대로 담게 된다.
따라서 실제 배열은 세로-가로 순으로 저장되지만,
사용하는건 헷갈리지 않고 통일되게 가로/세로 순으로 사용하면 된다.

위처럼 queue에도 j i 를 바꿔서 담아야한다.

• 2. make_pair를 사용하지 말자
     

위처럼 그냥 중괄호 치면 된다. 끝.

골드란 무엇인가 쓴맛을 본 것 같다.
그래도 도달할 수 없는 아득히 먼곳이 아닌 것 같아 재밌다.
계속 해보자.