[백준] 골드5 10026 적록색약

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

10026번: 적록색약

이 문제는 grid에 'R', 'G', 'B', 가 표현된 곳에서 같은 색상의 구역이 몇개나 있는지 구하는 문제이다.

 

즉, 하나의 색상을 탐색하기 시작해서 주변에 같은 색상이 있는지 탐색해야하는 문제이다.

그러면, dx, dy를 선언하여 현재 위치에서 상,하,좌,우로 이동할 수 있게끔 해야한다.

dx = [0, 0, 1, -1]

dy = [1, -1, 0, 0]

이제 어떤 알고리즘을 택할 것인지가 문제이다.

?? 우선 탐색을 해야하는데, 이 문제는 현재 위치의 주변에 있는 것들을 탐색을 해야한다. 

그러면, 적합한 알고리즘은 dfs 보다는 bfs이다.

 

첫번째의 경우 'R', 'G', 'B'의 구역들을 탐색해야하니, bfs에 넘겨주는 인수로는 현재 탐색을 시작한 좌표와 색상을 넘겨주었다.

다음 방문지에 갈 수 있는 조건인 visited == 0과 추가로 색상이 같은지를 비교해야하기 때문이다.

 

두번째의 경우 'R'과 'G'를 같은 경우로 생각하고, 'B'와 다르다고 생각해야한다. 적록색약 같은 경우 적색과 녹색을 구별할 수 없기 때문이다. 

처음에는 색상이 B일때, 그외 색상일 경우로 조건문을 사용하여 또 다른 bfs 함수를 만들었다. 

물론 잘 돌아가기도 하며, 문제를 맞추는데는 성공하였다. 

 

하지만, 너무 비효율적인 코드인것 같아서 숏코딩을 참고해보니, 첫번째의 경우를 완료한 뒤에 grid에서 'R'로 표현된 것을 'G'로 바꾸고 첫번째의 경우와 똑같은 동작을 수행하면 되는 것이였다.

 

그래서 처음 제출할때 1600B였던 코드의 길이가 1100으로 줄어드는 효과를 보았다.

1600 -> 1100

1일 1백준 21일째...