일기장
요즈음 주변 사람들로부터 표정이 어둡다는 이야기를 많이 듣는다. 그도 그럴것이 취준, 졸업준비를 동시에 하고 있으려니 현재 상황이 답답하게 느껴지기도 하고, 내가 과연 좋은 미래를 만들어나갈 수 있을까에 대한 의문도 든다.
언제부터 이렇게 된걸까. 나는 내 스스로 긍정파라고 생각해왔었다. 하지만 요즘 내 모습은 너무 비관적이고 현재 상황을 버겁게만 느끼는 사람인 것 같다.
너무 피상적인 미래만 생각하는 나 자신이 문제인 것 같다.
인생은 마라톤인데, 아직 절반도 못 온 상태에서 자꾸 결승선만을 생각하다보니 현재 호흡이 버거운 느낌이다. 생각을 바꿀 필요가 있지 않을까. 한걸음 한걸음에 집중하며 호흡에 신경쓰고 현재 상황을 즐기는 것이 가장 중요한 것인데.
알고리즘
문제에서는 도망치는 탈주범의 시작 인덱스와 이동시간(한 시간당 1의 거리를 이동할 수 있음) 그리고 전체 홀의 터널 구조물 번호를 제공한다.
문제에서 주어지는 터널 구조물의 타입은 다음과 같이 7개이고, 이 구조물의 모양에 따라 각 인덱스에 해당하는 홀의 이동 가능 경로가 생성된다.
예를 들어 N=5, M=6, R=2, C=1, L=3으로 위 표와 같은 경우가 주어졌을 때, 빨간 지점이 처음 탈주범에 도망치기 시작하는 위치이고
두 시간 뒤, 총 세시간의 시간이 흐른 뒤에는(처음 시작 지점에서의 소요시간을 1로 판정한다) 파란 지점까지 탈주범의 예상 이동가능 경로로 판단할 수 있는 것이다.
처음에 나는 이 문제를 읽자마자 DFS를 떠올렸다. 처음 주어진 탈주범의 시작 위치부터 시작해서, 탈주범이 주어진 시간 내 도달 할 수 있는 가장 먼 경로부터 하나하나 탐사하는 방법이 합리적이라고 생각한 것이다. 물론 DFS로 코드를 작성했을 때 짜기도 쉽고.
다음은 내가 DFS로 구현한 해당 코드이다. 결론부터 말하자면 아래 코드는 패스하지 못했기 때문에 알고리즘의 핵심 함수만 인용하고 나머지는 생략했다.
여기서 holes는 2차원 구조체 배열이고, 각 그리드에 주어진 터널 구조물에 따라 이동가능한 경로인 up/down/left/right를 불리언 변수로 가진다. 그리고 탈주범이 방문한 위치인지를 판단하는 visited 또한 불리언 변수이다.
위 코드의 모든 예외를 고려하여(탈주범의 이전 이동 위치와 해당 방문 인덱스의 터널 구조물의 해당 방향 설치 여부) 잘 작성했다고 생각하였으나, 문제가 있었다. 50개의 테스트케이스 중에서 35개만 계속 통과하고 나머지 15개를 잡지 못하는 것이었다.
위와 같은 테스트케이스에서 놓치게 되는 경로가 발생하였다. 위 댓글에 힌트를 얻어서 구현을 DFS -> BFS로 수정하게 되었다.
DFS 구현은 재귀함수로 구현하였을때 메모리에 쌓이는 함수 호출 정보가 스택으로 쌓이기 때문에 따로 호출 정보를 저장할 필요없이 메모리 상에 쌓이는 함수 호출 스택을 그대로 이용하면 된다.
그러나 BFS로 구현시 함수 호출 정보를 큐에 저장해야하기 때문에 DFS에서 구현한 알고리즘을 함수 호출 정보 구조체에 녹여내어 LIFO 함수 호출 스택을 FIFO 함수 호출 큐로 바꿨다.
일기장
손원평 작 ‘아몬드’ 中
…심 박사를 찾아간 어느 날이었다. 텔레비전 화면 속에서 폭격에 두 다리와 한쪽 귀를 잃은 소년이 울고 있다. 지구 어딘가에서 일어나는 전쟁에 관한 뉴스다. 화면을 보고 있는 심 박사의 얼굴은 무표정하다. 내 인기척을 느낀 그가 고개를 돌렸다. 나를 보자 다정하게 웃으며 인사를 건넸다. 내 시선은 미소 띤 박사의 얼굴 뒤로 떠오른 소년에게 향해 있었다. 나 같은 천치도 안다. 그 아이가 아파하고 있다는 걸. 끔찍하고 불행한 일로 고통스러워하고 있다는 걸.
하지만 묻지 않았다. 왜 웃고 있느냐고. 누군가는 저렇게 아파하고 있는데, 그 모습을 등지고 어떻게 당신은 웃을 수 있느냐고.
비슷한 모습을 누구에게서나 볼 수 있었기 때문이다. 채널을 무심히 돌리던 엄마나 할멈도 마찬가지였다. 너무 멀리 있는 불행은 내 불행이 아니라고, 엄마는 그렇게 말했었다.…