DFS를 이용한 BOJ 2667 단지번호붙이기

시즌 말 골드 승급이 제일 어려운 것 처럼,

실버 1 짜리 BOJ 2667번 단지번호붙이기 문제를 풀었다.

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

2667번: 단지번호붙이기

boj 2667 단지번호붙이기

와.... 물론 요즘 알고리즘 공부 한다고 했더니, 역시 DFS로 풀어야겠다라는 생각은 났다.

(나중에 찾아보니 BFS로도 가능하다고 한다. 사실 여기서는 탐색만 하면 상관이 없으니 둘다 가능할 듯 하다.)

그러나 무슨 알고리즘을 사용해야 하는지는 알고 있었지만, 손은 결국 얼어서 코드로 살려내지 못했다.

스스로의 저질스러운 코딩 실력에 감탄을 금치 못했다.

결국 책을 다시 읽고, 구글링을 통해 BFS의 기본 폼을 사용했다.

 

좌표의 0 또는 1의 값을 data라는 리스트에 받아서,

dx, dy의 벡터값을 잡아줬다.

또한 DFS라는 함수를 만들어서, 라인 아웃이 되는 경우를 없애고,

지나갔던 곳은 0으로 다시 메꿔준다.

좌표값을 상하좌우로 움직이면서, DFS에 계에속 넣는다. 

진짜... 이런 기본적인 예제도 실1이라니.

어쩌면 골딱이도... 멀지 않을지도?