[백준 12946] 육각 보드 [Java]

 

 

 

문제

http://boj.ma/12946

요약

• N * N 육각보드의 주어진 위치를 칠하기 위해 필요한 최소 색상의 수를 구하자.
• 한 변을 공유하는 두 칸은 다른 색상을 사용해야 한다.

---

풀이 과정

아이디어

인접한 칸은 현재 칸과 다른 색상을 사용해야 하므로, 그래프 탐색을 통해 주어진 위치에 RED - GREEN을 번갈아가며 부여하면 된다.

if (board[nx][ny] == 'X' && visited[nx][ny] == NOT_VISITED) {
    cnt = Math.max(cnt, dfs(nx, ny, mark == RED ? GREEN : RED));
}

색상 부여 후, 현재 칸과 인접한 칸이 동일한 색상을 가진다면 (RED-RED or GREEN-GREEN) 두 색상 외에 또 다른 색상(BLUE)가 필요하다.

3개의 색상은 육각보드의 임의의 주어진 모든 위치에 대응하기 위한 최소 색상이 되므로 더 이상의 탐색은 불필요하다.

if (visited[nx][ny] == mark) {
    // visited[nx][ny] is BLUE
    return 3;
}

최적화

기존에는 DFS 중 색상이 3개가 필요할 경우 더 이상의 탐색은 불필요하므로 return 3으로 탐색을 중단해주는 방식을 사용했다.

결과를 반환해 갱신하는 방법을 적용하고 있으므로

• 결과를 전역 변수에 저장
• BFS로 전환

하는 방법을 통해 최적화를 수행할 수 있다.

이 중 BFS로 전환하는 방식을 적용했다.

while (!queue.isEmpty()) {
  int[] cur = queue.poll();
  for (int d = 0; d < 6; ++d) {
      int nx = cur[0] + dx[d];
      int ny = cur[1] + dy[d];
      if (!isValid(nx, ny))
          continue;
      if (board[nx][ny] == 'X' && visited[nx][ny] == NOT_VISITED) {
          visited[nx][ny] = visited[cur[0]][cur[1]] == RED ? GREEN : RED;
          queue.add(new int[]{nx, ny});
          cnt = GREEN;
      }
      if (visited[nx][ny] == visited[cur[0]][cur[1]]) {
          // visited[nx][ny] is BLUE
          return 3;
      }
  }
}

 

하지만 N ≤ 50 이므로 큰 차이는 없었다.

성능 분석

• 시간 복잡도: $O(N^2)$
• 제출결과: Accepted / 104ms / 14,236KB

---

참고

문제

http://boj.ma/12946

12946번: 육각 보드

 

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/12946.java

problem-solving/baekjoon-online-judge/normal/12946.java at main · rogi-rogi/problem-solving