[25.03.17] algo 백준 7669 리뷰

25.03.17(Mon) 알고리즘 스터디 리뷰

문제 요약

• 바둑 게임에서 n×n 격자판에 놓인 흑돌과 백돌의 위치가 주어졌을 때 각 플레이어의 점수를 계산하는 문제
• 점수는 자신의 돌로 둘러싸인 빈 격자점 수의 합계

• 두 격자점은 $

  r-r’

  +

  c-c’

  =1$ 일 때 인접으로 판단

• 빈 영역은 인접한 모든 채워진 격자점이 한 플레이어의 돌일 때 그 플레이어의 영토
• 입력: 판 크기(n), 흑돌 수(b), 백돌 수(w)와 각 돌의 위치 좌표
• 출력: “White wins by X”, “Black wins by X” 또는 “Draw”

풀이방식

bfs
빈공간이 얼마나 많이 있고 그 빈공간이 어떤 돌로 둘러싸여 있는지를 확인하는 방식으로 풀이하기 위해서는 bfs를 활용하는 방식이 괜찮을 꺼라고 생각했다. 그래서 빈칸을 찾을때마다 bfs를 돌려서 빈공간을 모두 돌면서 주변부에 있는 돌이 빈공간이거나 어떤 돌로 둘러싸여 있는지를 확인하는 방식으로 풀이했다.

그런데 처음 풀이했던 것이 예제도 제대로 나오지 않는 경우가 생겼는데 이는 bfs를 돌릴때 같은 돌이 아니면 바로 bfs를 종료하는 방식으로 풀이했을때 문제가 생기는 것이였다. 이를 시각화하면, 아래 그림과 같이 예제의 세번째 케이스에서 오답이 나오게 되었다.

그래서 빈공간을 bfs로 모두 돌려서 중립인지 흑돌의 점수인지 흰돌의 점수인지를 판단하고 저장하는 방식으로 bfs를 종료해야지만이 문제를 풀이 할 수 있었다.

디버깅
이문제를 풀이할 때 왜 이런일이 일어나는지를 디버깅하는데에 문제가 있었다. 디버깅시에 출력을 찍어보고 그 출력을 통해서 고심해보는 과정이 필요할 것 같다. 알고리즘 풀이시에 디버깅을 할 때 문제가 생기는 로직을 확인하고 그 로직을 의심해보는 과정이 필요할 것 같다.

결과 코드