민혁이의 IT스토리

"절대 오지 않을 것 같았던 '정글'의 마지막 날이 드디어 1월 29일 오늘로 다가왔다. 돌아보면 5개월이라는 시간이 마치 한 편의 짧은 필름처럼 순식간에 지나갔지만, 그 필름 안에는 셀 수 없이 많은 밤과 치열한 고민들이 담겨 있다.0주차 미니 프로젝트를 마주하며 느꼈던 막막함이 엊그제 같은데, 어느덧 알고리즘의 늪을 지나고, 악명 높은 '핀토스'와 정면 승부하며 운영체제의 깊은 곳까지 파고들었다. 그리고 그 모든 과정의 결실인 '나만무(나만의 무기)' 프로젝트까지 마쳤다. 단순히 지식을 암기하는 시간이 아니었다. 스스로 문제를 정의하고 끝까지 해결해내는 법을 배우며, 내 한계를 몇 번이고 밀어붙였던 밀도 높은 5개월이었다. 이토록 무언가에 온전히 몰입해 본 경험이 또 있을까 싶을 정도로, 정글에서의 ..

https://www.acmicpc.net/problem/13565 문제 풀이 전략격자 형태의 지도에서 상단의 전류가 하단까지 연결되는지 확인해야 하므로 그래프 탐색 문제로 판단했다. 모든 정점을 방문해야 해서 DFS 혹은 BFS 모두 가능하지만, 구현이 간결한 재귀를 이용한 DFS로 구현해 보았다. BFS로 시도 했다가 추상화된 흐름문제의 요구 조건은 제일 바깥쪽(상단)에서 흘려보낸 전류가 안쪽(하단)까지 전달되는지 묻는 것이다. 단순하게 생각해보자. 일단 제일 윗줄(row=0)을 순회하며 전류(0)를 만나면 연결된 또 다른 길을 찾고, 바닥에 닿을 때까지 계속 탐색하면 된다. 이렇게 했을 때 시간복잡도는 $O(M \times N)$이다. 해결 과정탐색 시작점 설정: 제일 윗줄을 순회하며 전류(0)가..