백준 14466번 소가 길을 건너간 이유 6

🔒[문제 url]

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

🔑알고리즘

길을 2차원 vector에 표시하여, BFS내 다음 탐색 지점이 길을 통해 가야한다면 탐색하지 않는다.

• BFS 함수는 한 지점에 위치한 소가 길을 건너지 않고 만날 수 있는 소의 수를 반환한다.
  • 전체 쌍의 수에서 반환값의 합을 뺀 것이 출력 답안이 된다.
  • 이때 소가 위치한 지점을 1로 초기화하고, 해당 지점을 시작으로 한 BFS를 마치면 값을 -1로 바꾸어 쌍이 중복되지 않도록 해준다.

🐾부분 코드

void INPUT()
{
    IAMFAST
    cin >> n >> k >> r;
    for(int i = 0; i < r; i++)
    {
        int a,b,c,d; cin>>a>>b>>c>>d;
        road[a][b].emplace_back(c,d);
        road[c][d].emplace_back(a,b);
    }
    for(int i = 0; i < k; i++)
    {
        int a,b; cin >> a >> b;
        map[a][b] = 1;
    }
}

<입력 함수>
road라는 2차원 vector에 길의 정보를 저장한다.
map 2차원 배열에 소의 위치를 표시한다.

bool isRoad(int x,int y,int nx,int ny)
{
    for(auto [a,b] : road[x][y])
        if(a==nx && b==ny)
            return true;
    return false;
}

<길 판별 함수>
다음 탐색 지점이 길을 건너야한다면 true를 반환한다.
길을 건너야한다면 더이상 탐색하지 않는다.

int BFS(int sx,int sy)
{
    int canMeet = 0;

    memset(visited,false,sizeof visited);
    visited[sx][sy] = true;

    queue<pii> q;
    q.push({sx,sy});

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

        for(int i = 0; i < 4; i++)
        {
            auto [nx,ny] = dir[i];
            //범위 초과
            if(nx < 1 || n < nx || ny < 1 || n < ny) continue;
            //이미 방문한 지점
            if(visited[nx][ny]) continue;
            //길
            if(isRoad(x,y,nx,ny)) continue;

            if(map[nx][ny] == 1) canMeet++;
            visited[nx][ny] = true;
            q.push({nx,ny});
        }

    }
    return canMeet;
}

<BFS 함수>
탐색 시작 지점의 소가 길을 건너지 않고 만날 수 있는 소의 수를 반환한다.
소가 위치한 지점을 시작으로 BFS를 진행하며, 1인 지점을 만나면 return 값을 1 증가시킨다.

void SOLVE()
{
    int ans = 0,cnt = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(map[i][j] == 1)
            {
                ans += k - cnt - BFS(i, j);
                cnt++;
                map[i][j] = -1;
            }
    cout << ans;
}

<알고리즘 흐름>
소가 위치한 모든 지점에 대해 BFS를 탐색한다.
쌍이 중복되지 않도록 탐색이 끝난 지점은 -1로 표기한다.
ans는 최종적으로 (전체 쌍의 수) - (BFS 함수 반환값의 총합)이 된다.

🪄전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n,k,r;
int map[101][101];
typedef pair<int,int> pii;
vector<pii> road[101][101];
bool visited[101][101];
pii dir[4] = {{0,1},
              {0,-1},
              {1,0},
              {-1,0}};


void INPUT()
{
    IAMFAST
    cin >> n >> k >> r;
    for(int i = 0; i < r; i++)
    {
        int a,b,c,d; cin>>a>>b>>c>>d;
        road[a][b].emplace_back(c,d);
        road[c][d].emplace_back(a,b);
    }
    for(int i = 0; i < k; i++)
    {
        int a,b; cin >> a >> b;
        map[a][b] = 1;
    }
}

bool isRoad(int x,int y,int nx,int ny)
{
    for(auto [a,b] : road[x][y])
        if(a==nx && b==ny)
            return true;
    return false;
}

int BFS(int sx,int sy)
{
    int canMeet = 0;

    memset(visited,false,sizeof visited);
    visited[sx][sy] = true;

    queue<pii> q;
    q.push({sx,sy});

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

        for(int i = 0; i < 4; i++)
        {
            auto [nx,ny] = dir[i];
            //범위 초과
            if(nx < 1 || n < nx || ny < 1 || n < ny) continue;
            //이미 방문한 지점
            if(visited[nx][ny]) continue;
            //길
            if(isRoad(x,y,nx,ny)) continue;

            if(map[nx][ny] == 1) canMeet++;
            visited[nx][ny] = true;
            q.push({nx,ny});
        }

    }
    return canMeet;
}


void SOLVE()
{
    int ans = 0,cnt = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(map[i][j] == 1)
            {
                ans += k - cnt - BFS(i, j);
                cnt++;
                map[i][j] = -1;
            }
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

아주 솔직해져보자면.. 문제를 해결하고나서 남들은 어떻게 풀었나 포스팅을 확인해보면 내 코드가 웬만해서는, 사실 늘 더 깔끔했다.
그런데 정말 이 문제는 풀고나서도 기분이 별로 안 좋았다..😞
문제 이해도 너무 늦게하고 클린코드도 놓쳤다.
최근 ps에 소홀했던 것은 맞지만 문제가 심하게 안 풀려서 찝찝하다.
ps 포스팅을 조금 더 열심히 해봐야겠다.