문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

파이프를 최대한 벽에 밀착시켜 건설하면 된다. 따라서 Greedy로 풀 수 있다.

Algorithm

1. DFS를 하여 이동 가능한 인접한 칸으로 이동한다 (가장 위에 칸부터 조사하여, 가능한 경로를 탐색)
   • 현재 칸을 벽으로 채운다 (파이프를 건설할 수 있는 경로이든 아니든 체크하기 위함)
2. 오른쪽 끝에 도달하면 count += 1 해준다.

Data Structure

• gasMap[]: 파이프관 지도를 저장

결과

Other

시간 복잡도는 O(RC)이다.