백준 9205번 맥주 마시면서 걸어가기 JAVA

요구사항 정의

• T <= 50, N <= 100
• 집에서부터 편의점을 거쳐 페스티벌 장소까지 갈 수 있는지 체크

 

풀이 방법

난이도 기여탭에서 다른 사람들 의견처럼 이 문제를 보고 "그래프(BFS)로 풀어야겠다"라고 생각하기가 어려운 문제

나도 모르겠어서 태그를 확인하고 풀었다..

 

또한 문제가 복잡해서 20개의 맥주병을 들고있는데 편의점을 가면 채워진다고?? 반례를 생각하다가 오히려 머리가 복잡해졌다..

 

결국 현재 지점에서 1000 거리안에 편의점이나 도착점이 있는지를 체크하면서 BFS를 돌리면 되는 문제

 

 

방문한 편의점인지 체크하는 로직

문제를 풀 당시에는 1차원 visited 배열로 체크가 안될 것같아 equals를 오버라이딩하여 Set으로 체크를 하였다.

근데 풀고 보니 visited도 가능했다.. (오랫동안 문제를 안풀어서..)

 

for (int i = 0; i < stores.length; i++) {
	if(visited[i] || !accessible(e, p)) continue
    
    //queue에 넣는 로직
}

 

코드