백준 14466번 소가 길을 건너간 이유 6[C++]

1. 문제 풀이

1-1. 문제 핵심 설명

안녕하세요. 오늘 풀어볼 문제는 백준 14466번 소가 길을 건너간 이유 6입니다. 문제의 유형은 너비 우선 탐색의 응용문제였습니다. 단순한 너비 우선 탐색이 아니라 특정 경로에 "길"이 있다는 조건을 부여하고 길을 건너야만 만날 수 있는 두 소의 쌍을 구하는 문제이고 이 문제의 핵심은 "길"이 되겠습니다.

 

너비 우선 탐색을 알고 있다면 가장 먼저 떠올리는 의문은 "문제에서 설명하는 길이 무엇일까?" 일 것 같습니다. 백준에서 문제와 함께 제공한 테스트 케이스 입력은 아래와 같습니다.

3 3 3  → 목초지 크기, 소의 마릿수, 길의 개수 
2 2 2 3 → ( 2, 2 )에서 ( 2, 3 )으로 가는 경로가 "길"임
3 3 3 2
3 3 2 3
3 3 → 각 소의 위치 정보
2 2
2 3

 

이 정보를 그림으로 한 번 살펴보겠습니다.

자 여기서 초록색 막대는 길에 대한 정보이고 각 칸은 목초지고 목초지 안에 소 그림은 소의 위치에 맞추어 넣었습니다. 문제에서 요구한 사항은 길을 건너야만 만날 수 있는 소들의 쌍입니다.

( 2, 2 )에서 ( 2, 3 )으로 가는 길은 위 그림과 같이 길을 통해서 가는 방법과 길을 피해서 돌아서 가는 방법이 있습니다. 문제에서 길을 통해서야만 만날 수 있는 소들의 쌍을 구하라고 요구했으니 우선순위는 길을 피해서 돌아가는 방법입니다.

 

 그렇다면 이 부분을 구현하는 방법을 강구해봅시다. 어떤 임의의 목초지에서 인접한 상하좌우 목초지로 자유롭게 이동이 가능합니다. 그리고 그중 "길"인 곳이 있고 아닌 곳이 있습니다. "길"인 곳을 피해 너비 우선 탐색을 진행하게 된다면 방문 배열에서 "길"을 통하지 않고도 만날 수 있는 소들의 대한 정보를 알 수 있게 됩니다. 즉 "길"이 아니라 바리케이드가 있다고 생각을 해보는 겁니다.

그러면 ( 2, 2 ), ( 2, 3 )만 길을 통하지 않고 만날 수 있는 쌍이되고 ( 2, 2 ), ( 3, 3 )과 ( 2, 3 ), ( 3, 3 ) 두 쌍이 만날 수 없으므로 2가 정답이 됩니다.

 

요약 : "길"인 곳을 피해서 너비 우선 탐색을 진행한다.

1-2. "길" 인지 아닌지 판별

이제 너비 우선 탐색을 진행할 때, 이동할 곳이 "길"인지 아닌지 판별하기 위해서 길 정보를 매핑해 봅시다. 우선 너비 우선 탐색을 하기 위해선 아래와 같은 변수들이 필요합니다.

bool vis[105][105][105]; // vis[x][y][s] : s 번째 소의 방문 배열
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

 

예를 들어 ( 2, 2 )에서 ( 2, 3 )으로 가는 경로가 "길"이라고 입력이 주어졌다고 해봅시다. 임의의 칸 하나는 상하좌우 4개 방향으로 이동이 가능합니다. 그중 어느 방향이 길인지에 대해서 기록해 놓는다면 나중에 너비 우선 탐색을 진행할 때 조건문을 하나 추가해서 길을 통해 이동하는 것을 방지할 수 있게 됩니다. 

 

구현 코드는 아래와 같습니다.

  // is_road[x][y][1] = 1 : (x, y)에서 1번 째 방향이 길이다
  bool is_road[105][105][4];
  cin >> n >> k >> r; // 목초지 크기, 소의 마릿수, 길의 개수 입력
  while(r--){
    int cx, cy, nx, ny;
    cin >> cx >> cy >> nx >> ny; // 길 정보 저장
    // (cx, cy)에서 4가지 방향에 대한 조사
    for(int dir = 0; dir < 4; dir++){
      int px = cx + dx[dir];
      int py = cy + dy[dir];
      // "길"인 방향을 찾았음
      if(px == nx && py == ny){
        is_road[cx][cy][dir] = 1;
        is_road[nx][ny][(dir+2)%4] = 1; // (nx, ny)에서 (cx, cy)로 이동가는 경로도 길
      }
    }
  }

 

1-3. 시간 복잡도 분석

목초지의 최대 크기는 100×100이므로 너비 우선 탐색의 시간 복잡도는 O(10000)입니다. 소는 최대 100마리만 존재합니다. 여기서 각 소마다 너비 우선 탐색을 진행해야 각각의 소마다 "길"을 통해야만 이동할 수 있는지 알 수 있으므로 시간복잡도는 O(1,000,000)이 됩니다. 시간제한은 2초이므로 각 소마다 너비 우선 탐색을 진행해도 상관이 없음을 알 수 있습니다.

 

요약 : 각각의 소마다 너비 우선 탐색을 진행해도 시간 제한 내에 통과가 가능하다.

2. C++ 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb;
#define X first
#define Y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const char nl = '\n';
const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };
bool is_road[105][105][4];
bool vis[105][105][105];
pi pos[105];
int n, k, r;

void bfs(pi init, int state){
  queue<pi> q;
  vis[init.X][init.Y][state] = 1;
  q.push(init);
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    for(int dir = 0; dir < 4; dir++){
      if(is_road[cur.X][cur.Y][dir]) continue;
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
      if(vis[nx][ny][state]) continue;
      vis[nx][ny][state] = 1;
      q.push({nx, ny});
    }
  }
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k >> r;
  while(r--){
    int cx, cy, nx, ny;
    cin >> cx >> cy >> nx >> ny;
    for(int dir = 0; dir < 4; dir++){
      int px = cx + dx[dir];
      int py = cy + dy[dir];
      if(px == nx && py == ny){
        is_road[cx][cy][dir] = 1;
        is_road[nx][ny][(dir+2)%4] = 1;
      }
    }
  }

  for(int i = 0; i < k; i++) cin >> pos[i].X >> pos[i].Y;

  int ans{};
  for(int i = 0; i < k-1; i++){
    bfs(pos[i], i);
    for(int j = i+1; j < k; j++){
      if(!vis[pos[j].X][pos[j].Y][i]) ans++;
    }
  }
  cout << ans;
}