[BOJ]9205:맥주 마시면서 걸어가기(BFS, 플로이드)

작년엔 보고 헉 하고 넘겼던 문제

오늘도 보고 헉 하긴 함;;

 

BFS ver.

while (! queue.isEmpty()){
                myPoint cur = queue.poll();
                if(cur.x == cvs[N][0] && cur.y == cvs[N][1]) {
                    isHappy = true;
                    break;
                }

                for(int i = 0; i < N+1; i++){
                    int dist = calcDist(cur.x, cur.y, cvs[i][0], cvs[i][1]);
                    if(!vis[i] && dist <= 1000){
                        vis[i] = true;
                        queue.offer(new myPoint(cvs[i][0], cvs[i][1]));
                	}
       			}
}

플로이드 알고리즘 ver.

원래 플로이드는 3중 for문 안에서 가중치값을 min으로 갱신하지만 이문제는 x, y축이 각각 1000 이하인지 확인하기만 하면 된다

 

for (int k = 0; k < N + 2; k++) {
                for (int i = 0; i < N + 2; i++) {
                    for (int j = 0; j < N + 2; j++) {
                        if (i == j || i == k || j == k) continue;
                        if (chk[i][k] && chk[k][j]) {
                            chk[i][j] = true;
                        }
                    }
                }
}

 

결과 비교

예상대로 bfs가 훨씬 빠르게 돌아간다.

플로이드는 n이 작아야 가능한 이야기. 여기서는 n이 100이하라 통과된듯

플로이드:

bfs:

 

 

이제 나도 맥주마시러!