(JAVA) 백준 14867번 : 물통 --- [BFS]

www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

*** 정골에서 코드를 돌려보며 틀린 테스트케이스를 확인할 수 있습니다.

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2383&sca=99&sfl=wr_subject&stx=%EB%AC%BC%ED%86%B5

JUNGOL

 

 

안녕하세요.

 

난이도 골드2 의 BFS 문제 입니다.

 

 

저에겐 생각보다 어렵네요..

 

 

음..

 

조건이 까다롭고,

시간 초과에 유의하면서 풀어야하기 때문에 어렵다고 느껴졌습니다.

 

 

단순히 BFS 문제라고 생각하면 안되는게

 

x, y 좌표 값을 가지고 이를 움직이면서 목적지까지 가는 BFS 이지만

최대 크기가 각각 100000 입니다.

 

 

오우!

사이클 방지를 위해서 이동 시 중간지점마다 방문 체크를 해줘야 합니다만..

 

그런데 100000 * 100000 크기의 2차원 boolean 배열을 생성할 수 없습니다. Heap Space가 부족하기 때문이죠.

 

 

그럼 다른 방법으로 방문 체크를 해줘야 하는데

 

중요한 것은 반드시 모든 100000 * 100000 개수가 필요 없다는 것입니다.

 

 

방문한 것들만 별도로 넣고, 새로운 지점에 갈 때마다 이전에 방문한 것들과 비교하면 되죠!

 

이렇게 데이터를 넣는것보다 조회의 비중이 크고, 조회 시 시간이 적게 걸리는 자료구조를 사용하여 방문 체크를 해줘야 합니다.

 

 

저는 HashSet을 사용했습니다. 조회에 있어 HashMap과 쌍두마차인 HashSet을 이용해서

 

"x_y" 라는 별도의 문자열 규칙을 만들어 이를 넣고 조회(Contains)하면서 중복을 체크했기 때문에 시간 초과가 발생하지 않게 되었습니다.

 

 

또 하나 더 말씀드리자면

이동할 수 있는 경우의 수는 6가지 입니다. (Full x, Full y, Empty x, Empty y, Move x->y, Move y->x)

그래서, Queue에서 poll한 원소를 6가지 방법으로 이동시킨 후 다시 Queue에 넣는 BFS 알고리즘을 활용했습니다!

 

 

하지만, 실제 까보면 이동할 수 있는 경우의 수는 생각보다 적습니다.

실제 이동가능한지 예외처리를 해두면 좀 더 효율적인 매커니즘이 되죠. (소스코드를 참고해주세요!)

 

 

나머지 부분은 소스코드를 참고하시면 해결 가능할 겁니다.

 

이상입니다.

감사합니다!

 

 

 

소스코드

---