(JAVA) 백준 2931번 : 가스관

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

2931번: 가스관

은근 시간이랑 손이 많이 가는 문제였다..

 

시간을 반나절 허비한 듯 하다.

 

썩 좋지 않은 문제라고 생각되는게

경우의 수를 규칙이 아닌 약간의 하드코딩으로 해야 풀 수 있었기 때문이다...

 

 

여러 함수를 구현한 다음

그 함수들을 사용해서 해결했다.

 

DFS 방식도 사용했다.

 

 

매커니즘

---

 이 문제의 핵심은 밑 캡쳐 화면에서 형광펜으로 칠한 문장이라고 생각한다.

 

  " 가스는 블록을 통해 양방향으로 흐를 수 있다. "

 

저 말은 뭐냐면

그림처럼 무조건 M -> Z로 가는 것이 아니라

M -> Z, Z -> M 이라는 두 방향이 존재한다는 뜻이다.

 

이를 응용한다면

저 연결된 파이프들 중 하나가 없어졌을 때,

 

M에서 시작해서 없어진 파이프까지 와

Z에서 시작해서 없어진 파이프까지 를

 

DFS를 사용해서 쉽게 없어진 파이프의 좌표를 찾을 수 있다.

** 이에 더해, 없어진 파이프 이전까지 탐색하면서 가스의 방향을 찾을 수 있다!!

 

 

 

이렇게 가운데가 비어있다면

 

M에서 시작한 가스는 비어있는 파이프 전까지 아래 방향

Z에서 시작한 가스는 비어있는 파이프 전까지 오른쪽 방향

 

을 얻을 수 있고, 이를 바탕으로 파이프 모양까지 유추할 수 있다.

 

그럼 문제 해결!

 

** 단, 십자 파이프일 경우도 존재하므로 나의 경우에는

빈 파이프 상하좌우에 있는 파이프를 찾아

이미 가스가 방문한 적이 있는지 여부를 파악하여

만약 방문한 적이 없는 파이프가 존재한다면 '십자파이프', 존재하지 않으면 'ㄱ 또는 ㄴ자 파이프' 로 생각했다.

 

 

결국, 흐름은

 

 1) M에 인접한 파이프를 찾는다.

 2) Z에 인접한 파이프를 찾는다.

 3) 1)에 찾은 파이프(M)부터 시작하여 DFS방식으로 비어있는 파이프의 위치와 가스의 방향을 찾는다.

 4) 2)에 찾은 파이프(Z)부터 시작하여 DFS방식으로 비어있는 파이프의 위치와 가스의 방향을 찾는다.

 5) 3), 4)에서 찾은 두 방향을 가지고 비어있는 파이프의 모양(block)을 유추한다.

 6) 결과 출력

 

 

각 과정에 필요한 함수들을 만들다보니 길어지긴 했다..

 

 

 

깃허브에서 소스코드 전체 보기(함수 별 주석 포함)