백준 10026 : 적록색약

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

문제

1 2 3

완성된 코드

풀이

  • BFS를 활용하여 같은 색으로 이루어진 구역의 개수를 탐색한다. 적록색약인 사람과 아닌 사람은 구분되어야 하므로 따로 계산하여 그 개수를 함께 출력한다.

BFS

inside, offset

  • BFS 안에서 쓸 조건문 중 현재 좌표가 전체 구역 안에 있는지를 확인하는 함수를 선언한다.
  • 이후 dx, dy라고도 할 수 있는 offset, 즉 이동 거리를 배열로 선언한다.

BFS

  • 시작 좌표를 q에 넣는다.
  • 현재 좌표를 q에서 꺼내어 상하좌우로 색을 탐색한다.
  • 전체 구역 안에 존재 & 방문하지 않은 좌표 & 같은 색이면
    vstd 배열에서 현재 좌표+offset 의 위치를 방문한 좌표로(1) 변경하고 탐색을 계속하기 위해 q에 현재 좌표+offset를 삽입한다.

    ❓ 왜 BFS 함수 안에 return 값이 없는가?
  • ✌️BFS 함수가 실행된 횟수 자체✌️를 count하기 위해서
  • 따라서 BFS 함수를 실행&종료한다는 게 중요하다.
  • 처음에는 return 값을 어떤 걸로 해야 할까, 고민했는데 BFS 함수 안에 적록색약이 아닌 사람 + 적록색약인 사람을 넣으려고 하니 코드가 복잡해지고 중복되는 부분도 많아져서 실행&종료의 한 사이클을 count 하기로 했다.

❌ 적록색약이 아닌 사람 ❌

  • 방문하지 않은 좌표에 대하여 BFS 함수를 수행하고 수행한 횟수를 반환한다.

⭕ 적록색약인 사람 ⭕

  • 적록색약은 빨간색과 초록색을 구분하지 못하기 때문에 그냥 애초부터 R을 G로 바꿔주고 탐색을 시작한다.
  • 방문하지 않은 좌표에 대하여 BFS 함수를 수행하고 수행한 횟수를 반환한다.

댓글남기기

참고