코딩개발로 물장구치는 개발자

안녕하세요 Dibrary입니다. 이번에는 제가 BFS/DFS에 아주 약간? 자신감이 생겨서 도전했다가 몇 시간을 .. 날려버린 문제를 정리해보겠습니다. 알고보니 BFS/DFS같은 그래프 풀이방법 만 쓰는 게 아니라, 여기에 모든 경우의 수 까지 같이 확인해야 하는 문제였어서 처음 접한 저는 매우 어려웠었습니다. 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 처음에 문제를 보고 곧바로 "BFS를 쓰믄 되겠다! " 라는 생각이 제일 먼저 떠올랐습니다. 왜냐하면, 문제에서 "바이러스는 퍼져나갈 수 있다" 라고 나왔기 때문이죠...

안녕하세요 Dibrary입니다. 이번에는 그래프 탐색 + 약간의 생각을 사용해야 풀 수 있는 문제 입니다. (참고로 저는 생각을 하지 못해서 어려웠었죠;;) 이 문제를 보자마자 떠오른 생각은 아 확산이 되네? BFS또는 DFS로 퍼뜨려 나갈 수 있겠다. 근데 시작점이 한 개가 아니네....? 헐 생각 1번을 구현하기는 어렵지 않습니다. 문제는 '시작점'이 여러 개 인 것을 해 본 적이 없다는 것이었죠. 이 문제를 풀 때 생각해볼 2가지 아이디어가 있습니다. 먼저 잘 생각해 보면 시작점이 여러 개인 것은 그다지 중요하지 않습니다. BFS를 사용한다고 할 때, 우리는 해당 '위치'에 대해서 뭘 고려할까요? '방문 했느냐' / '방문 안했느냐' 입니다. 즉, 시작점이 여러 개라 한들 방문해버리면 어차피 거긴 ..