백준 2423 - 전구를 켜라

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

 

힌트

0-1 BFS를 이용하면 가중치가 0과 1로만 이루어진 그래프에서 $O(V + E)$의 시간복잡도로 문제를 해결할 수 있다.

 

이를 문제에 형태에 맞춰 구현하는 방법을 생각해본다.

 

만약 문제를 틀린 상태에서 이 게시글을 보고 있는 것이라면 다음 격자로 갈 수 있는 조건을 다시 확인해보도록 하자.

---

풀이

문제에 주어진 회로는 최대 8방향으로 탐색할 수 있음을 보여주고 있다.

 

그리고 회로가 가질 수 있는 위상은 두가지이므로 좌표와 위상을 나타내는 3차원 배열을 생성해서 회로를 돌렸을 때 가중치를 1로 생각해서 0-1 BFS를 수행하면 된다.

 

다만 회로를 돌린다고 무조건 갈 수 있는 것이 아니다.

 

다음 두 경우를 보자.

 

 

왼쪽의 경우 오른쪽 오른쪽 위나 왼쪽 아래는 어떻게 해도 갈 수 있는 방법이 존재하지 않는다.

 

마찬가지로 오른쪽의 경우 왼쪽 위나 오른쪽 아래로 갈 수 있는 방법은 존재하지 않는다.

 

대각선을 이동할 때 다음 경우를 고려해서 탐색을 수행해야 올바르지 않은 답을 출력하는 경우를 방지할 수 있다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int r, c;
vector<string> circuit;
int cost[500][500][2];
int straight_r[4] {1, -1, 0, 0};
int straight_c[4] {0, 0, 1, -1};
int diagonal_r[4] {1, -1, 1, -1};
int diagonal_c[4] {1, -1, -1, 1};
int conv[255];

inline bool unable(int &_r, int &_c) { return (_r < 0 || _c < 0 || _r >= r || _c >= c); }

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

  conv['/'] = 1, conv['\\'] = 0;
  fill(&cost[0][0][0], &cost[0][0][0] + 500 * 500 * 2, 1e9);
  cin >> r >> c;

  circuit.resize(r);
  for (int i = 0; i < r; ++i)
    cin >> circuit[i];

  deque<vector<int>> q;
  q.push_back({0, 0, 0});

  if (circuit[0][0] == '/')
    cost[0][0][0] = 1;
  else
    cost[0][0][0] = 0;

  while (q.size())
  {
    auto cur = q.front();
    q.pop_front();

    int cr = cur[0], cc = cur[1], cdir = cur[2];
    int next_circuit;
    int next_cost;
    int nr, nc;

    for (int i = 0; i < 4; ++i)
    {
      nr = cr + straight_r[i], nc = cc + straight_c[i];
      if (unable(nr, nc))
        continue;
      
      next_cost = cost[cr][cc][cdir];

      if (cdir == conv[circuit[nr][nc]])
        ++next_cost, next_circuit = (cdir + 1) % 2;
      else
        next_circuit = conv[circuit[nr][nc]];
            
      if (next_cost >= cost[nr][nc][next_circuit])
        continue;
      
      cost[nr][nc][next_circuit] = next_cost;
      if (next_cost == cost[cr][cc][cdir])
        q.push_front({nr, nc, next_circuit});
      else
        q.push_back({nr, nc, next_circuit});
    }

    if (!cdir)
    {
      for (int i = 0; i < 2; ++i)
      {
        nr = cr + diagonal_r[i], nc = cc + diagonal_c[i];
        if (unable(nr, nc))
          continue;
        
        next_cost = cost[cr][cc][cdir];

        if (cdir != conv[circuit[nr][nc]])
          ++next_cost;

        if (next_cost >= cost[nr][nc][cdir])
          continue;

        cost[nr][nc][cdir] = next_cost;
        if (next_cost == cost[cr][cc][cdir])
          q.push_front({nr, nc, cdir});
        else
          q.push_back({nr, nc, cdir});
      }
    }
    else
    {
      for (int i = 2; i < 4; ++i)
      {
        nr = cr + diagonal_r[i], nc = cc + diagonal_c[i];
        if (unable(nr, nc))
          continue;
        
        next_cost = cost[cr][cc][cdir];

        if (cdir != conv[circuit[nr][nc]])
          ++next_cost;
        if (next_cost >= cost[nr][nc][cdir])
          continue;

        cost[nr][nc][cdir] = next_cost;
        if (next_cost == cost[cr][cc][cdir])
          q.push_front({nr, nc, cdir});
        else
          q.push_back({nr, nc, cdir});
      }
    }
  }

  int ans = cost[r - 1][c - 1][0];
  if (ans == 1e9)
    cout << "NO SOLUTION";
  else
    cout << cost[r - 1][c - 1][0];
}

제출 기록