boj 9205 맥주 마시면서 걸어가기

www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

1번 정점 : 시작점

2번 ~ N + 1번 정점 : 편의점

N + 2번 정점 : 도착점

 

bfs와 플로이드 와샬 두 가지 방법을 이용할 수 있습니다.

 

먼저 bfs 풀이로는 N^2으로 각 정점들 사이의 거리가 1000이하인 간선만 그래프화 시켜줍니다.

그 다음 1번정점으로 시작하여 bfs로 인접한 모든 정점을 방문한 후에 N + 2번 정점을 방문하였는지 확인합니다.

N + 2번 정점을 방문 하였으면 happy, 방문 안했으면 sad를 출력합니다.

 

 

플로이드 풀이로는 N^2으로 각 정점들 사이의 거리가 1000이하면 dis[i][j] = true를 하여 간선체크를 해줍니다.

그 다음 플로이드를 사용하는데 i ~ k번을 지나갈 수 있고, k ~ j번을 지나갈 수 있으면 i ~ j번을 지나갈 수 있습니다.

따라서 dis[i][k] && dis[k][j]이면 dis[i][j] = true를 해줍니다.

dis[1][N+2] = true면 happy, false면 sad를 출력합니다.

 

bfs

플로이드 와샬

 

실행 시간은 bfs쪽이 좀 더 빨랐습니다.

 

 

[bfs]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> graph[] = new ArrayList[103];
    static boolean visit[] = new boolean[103];
    static int list[][] = new int[103][2];
    static int N;
 
    static void bfs() {
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(1);
        visit[1] = true;
        while (!dq.isEmpty()) {
            int x = dq.poll();
 
            for (int i = 0; i < graph[x].size(); i++) {
                int next = graph[x].get(i);
 
                if (visit[next])
                    continue;
 
                dq.add(next);
                visit[next] = true;
            }
        }
 
        if (visit[N + 2])
            sb.append("happy\n");
        else
            sb.append("sad\n");
    }
 
    static boolean getDis(int a[], int b[]) {
        return (Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1])) <= 1000 ? true : false;
    }
 
    static void func() {
        for (int i = 1; i <= N + 1; i++) {
            for (int j = i + 1; j <= N + 2; j++) {
                if (getDis(list[i], list[j])) {
                    graph[i].add(j);
                    graph[j].add(i);
                }
            }
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N + 2; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
    }
 
    static void init() {
        Arrays.fill(visit, false);
        for (int i = 1; i <= N + 2; i++) {
            graph[i] = new ArrayList<>();
        }
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
            init();
            func();
            bfs();
        }
        System.out.println(sb.toString());
    }
}

 

 

[플로이드 와샬]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[][] = new int[103][2];
    static boolean dis[][] = new boolean[103][103];
    static int N;
 
    static int getDis(int x, int y, int tx, int ty) {
        return Math.abs(x - tx) + Math.abs(y - ty);
    }
 
    static void func() {
        for (int i = 1; i <= N + 1; i++) {
            for (int j = i + 1; j <= N + 2; j++) {
                if (getDis(list[i][0], list[i][1], list[j][0], list[j][1]) <= 1000) {
                    dis[i][j] = true;
                    dis[j][i] = true;
                }
            }
        }
 
        for (int k = 1; k <= N + 2; k++) {
            for (int i = 1; i <= N + 2; i++) {
                for (int j = 1; j <= N + 2; j++) {
                    if (dis[i][k] && dis[k][j])
                        dis[i][j] = true;
                }
            }
        }
 
        if (dis[1][N + 2])
            sb.append("happy\n");
        else
            sb.append("sad\n");
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N + 2; i++) {
            st = new StringTokenizer(br.readLine());
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }
    }
 
    static void init() {
        for (int i = 1; i <= N + 2; i++)
            Arrays.fill(dis[i], false);
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        for (int t = 1; t <= tc; t++) {
            input();
            func();
            init();
        }
 
        System.out.println(sb.toString());
    }
}