백준 13265 색칠하기

링크 : https://www.acmicpc.net/problem/13265

문제 설명

문제

어린 토니킴은 색칠공부를 좋아한다.

토니킴은 먼저 여러 동그라미와 동그라미 두 개를 연결하는 직선들 만으로 그림을 그리고 (모든 동그라미들 사이에 직선이 있을 필요는 없다), 연결된 두 동그라미는 서로 색이 다르게 되도록 색을 칠하고자 한다.

이 그림을 색칠하는데 필요한 최소의 색의 개수를 구하는 문제는 어렵기 때문에 토니킴은 2 가지 색상으로 색칠이 가능한지의 여부만을 알고 싶어한다.

동그라미들의 번호와 동그라미들이 서로 연결된 직선에 대한 정보가 주어졌을 때, 이 동그라미들이 2 가지 색상으로 색칠이 가능한지 알아내자.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T 가 주어진다.

그 다음 줄부터 각 테스트 케이스에 대해 동그라미의 개수 n(1 ≤ n ≤ 1000)과 직선들의 개수 m(1 ≤ m ≤ 100,000)이 주어지고, 그 다음 줄부터 m 줄에 걸쳐 동그라미들이 연결된 직선에 대한 정보가 주어진다. (x y)로 주어지면 동그라미 x와 동그라미 y가 직선으로 서로 연결되었다는 의미이다. 동그라미들의 번호는 1 부터 n 까지이다.

출력

각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다.

---

문제 풀이

bfs를 이용하여 문제 풀이

bfs함수

- circles : 동그라미 사이의 연결된 선 정보

- s : 검사를 진행할 동그라미 정보 (동그라미 값, 칠해야할 색)

- circles_color : 동그라미 색 정보

로직 설명

- 현재 target 동그라미에 연결되어 있는 선을 기준으로 검사 (circles[target][i] 가 1인 경우 -> 연결되어있다.)

  - 연결된 동그라미가 이미 색이 칠해져있을 때, 같은 색일 경우 impossible 리턴

  - 칠해진 색이 없다면 반대되는 색정보를 저장(circles_color[i])하고 연결 정보(circle) 초기화

const inputs = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const bfs = (circles, s, circles_color) => {
  // 색은 2, -2로 칠함
  while (s.length > 0) {
    let [target, color] = s.shift();
    // target에 인접한 다른 원을 반대 색으로 칠함
    for (let i = 0; i < circles[target].length; i++) {
      let circle = circles[target][i];
      if (circle === 0) continue;
      // i번째 동그라미의 색을 구함
      let circle_color = circles_color[i];
      // 색이 같으면 반대 색으로 칠하는게 불가능
      if (circle_color === color) {
        return console.log("impossible");
      } else if (circle_color === 0) {
        // 색이 없으면 반대 색으로 칠함
        circles_color[i] = -color;
        s.push([i, -color]);
        circles[target][i] = -color;
        circles[i][target] = -color;
      }
    }
  }
  return console.log("possible");
};

const t = parseInt(inputs[0]);
let index = 0;
for (let i = 0; i < t; i++) {
  const [n, m] = inputs[1 + index + i].split(" ").map(Number);

  let circles = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => 0)
  );
  let circles_color = Array.from({ length: n }, () => 0);
  let s = [];

  for (let j = 1; j <= m; j++) {
    let [x, y] = inputs[1 + index + i + j].split(" ").map(Number);
    if (j === 1) {
      s.push([x - 1, 2]);
      circles_color[x - 1] = 2;
    }
    circles[x - 1][y - 1] = 1;
    circles[y - 1][x - 1] = 1;
  }

  bfs(circles, s, circles_color);
  index += m;
}

---

결론

bfs로 색을 칠해가면서 불가능한 경우의 로직을 잘 작성해야 정상 동작함