๐Ÿ“– [๋ฐฑ์ค€์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€์ด] Q.9205 ๋งฅ์ฃผ ๋งˆ์‹œ๋ฉด์„œ ๊ฑธ์–ด๊ฐ€๊ธฐ ๋ฌธ์ œ ํ’€์ด - java

๐Ÿ“– ๋ฌธ์ œ

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

์†ก๋„์— ์‚ฌ๋Š” ์ƒ๊ทผ์ด์™€ ์นœ๊ตฌ๋“ค์€ ์†ก๋„์—์„œ ์—ด๋ฆฌ๋Š” ํŽœํƒ€ํฌํŠธ ๋ฝ ํŽ˜์Šคํ‹ฐ๋ฒŒ์— ๊ฐ€๋ ค๊ณ  ํ•œ๋‹ค. ์˜ฌํ•ด๋Š” ๋งฅ์ฃผ๋ฅผ ๋งˆ์‹œ๋ฉด์„œ ๊ฑธ์–ด๊ฐ€๊ธฐ๋กœ ํ–ˆ๋‹ค.

์ถœ๋ฐœ์€ ์ƒ๊ทผ์ด๋„ค ์ง‘์—์„œ ํ•˜๊ณ , ๋งฅ์ฃผ ํ•œ ๋ฐ•์Šค๋ฅผ ๋“ค๊ณ  ์ถœ๋ฐœํ•œ๋‹ค. ๋งฅ์ฃผ ํ•œ ๋ฐ•์Šค์—๋Š” ๋งฅ์ฃผ๊ฐ€ 20๊ฐœ ๋“ค์–ด์žˆ๋‹ค. ๋ชฉ์ด ๋งˆ๋ฅด๋ฉด ์•ˆ๋˜๊ธฐ ๋•Œ๋ฌธ์— 50๋ฏธํ„ฐ์— ํ•œ ๋ณ‘์”ฉ ๋งˆ์‹œ๋ ค๊ณ  ํ•œ๋‹ค.

์ƒ๊ทผ์ด์˜ ์ง‘์—์„œ ํŽ˜์Šคํ‹ฐ๋ฒŒ์ด ์—ด๋ฆฌ๋Š” ๊ณณ์€ ๋งค์šฐ ๋จผ ๊ฑฐ๋ฆฌ์ด๋‹ค. ๋”ฐ๋ผ์„œ, ๋งฅ์ฃผ๋ฅผ ๋” ๊ตฌ๋งคํ•ด์•ผ ํ•  ์ˆ˜๋„ ์žˆ๋‹ค. ๋ฏธ๋ฆฌ ์ธํ„ฐ๋„ท์œผ๋กœ ์กฐ์‚ฌ๋ฅผ ํ•ด๋ณด๋‹ˆ ๋‹คํ–‰ํžˆ๋„ ๋งฅ์ฃผ๋ฅผ ํŒŒ๋Š” ํŽธ์˜์ ์ด ์žˆ๋‹ค.

ํŽธ์˜์ ์— ๋“ค๋ ธ์„ ๋•Œ, ๋นˆ ๋ณ‘์€ ๋ฒ„๋ฆฌ๊ณ  ์ƒˆ ๋งฅ์ฃผ ๋ณ‘์„ ์‚ด ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ, ๋ฐ•์Šค์— ๋“ค์–ด์žˆ๋Š” ๋งฅ์ฃผ๋Š” 20๋ณ‘์„ ๋„˜์„ ์ˆ˜ ์—†๋‹ค.

ํŽธ์˜์ , ์ƒ๊ทผ์ด๋„ค ์ง‘, ํŽœํƒ€ํฌํŠธ ๋ฝ ํŽ˜์Šคํ‹ฐ๋ฒŒ์˜ ์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ƒ๊ทผ์ด์™€ ์นœ๊ตฌ๋“ค์ด ํ–‰๋ณตํ•˜๊ฒŒ ํŽ˜์Šคํ‹ฐ๋ฒŒ์— ๋„์ฐฉํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

๐Ÿ” ์ ‘๊ทผ๋ฒ•

Q.9205 ๋งฅ์ฃผ ๋งˆ์‹œ๋ฉด์„œ ๊ฑธ์–ด๊ฐ€๊ธฐ ๋ฌธ์ œ ํ’€์ด์ž…๋‹ˆ๋‹ค.

๋ฌธ์ œ์—์„œ n+2 ๊ฐœ ์ค„์— ์ƒ๊ทผ์ด๋„ค ์ง‘, ํŽธ์˜์  , ํŽœํƒ€ํฌํŠธ ๋ฝ ํŽ˜์Šคํ‹ฐ๋ฒŒ ์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

์ƒ๊ทผ์ด๋„ค ์ง‘์—์„œ ํŽœํƒ€ํฌํŠธ ๋ฝ ํŽ˜์Šคํ‹ฐ๋ฒŒ๊นŒ์ง€ ๋„์ฐฉํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์—†๋Š”์ง€๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด ์ •๋‹ต์ž…๋‹ˆ๋‹ค.

๋‹จ, ์ƒ๊ทผ์ด๊ฐ€ ๋‹ค๋ฅธ ์ง€์ ์œผ๋กœ ์ด๋™ํ•  ๋•Œ ๋ชฉ์ด ๋งˆ๋ฅด๋ฉด ์•ˆ๋˜๊ธฐ ๋•Œ๋ฌธ์— 50๋ฏธํ„ฐ์— ํ•œ ๋ณ‘์”ฉ์„ ๋งˆ์‹ค ์ˆ˜ ์žˆ์–ด์•ผํ•ฉ๋‹ˆ๋‹ค.

๋งฅ์ฃผ ํ•œ ๋ฐ•์Šค๋ฅผ ๋“ค๊ณ  ์ถœ๋ฐœํ•˜๊ณ  ํ•ญ์ƒ ๋งฅ์ฃผ ํ•œ ๋ฐ•์Šค๊ฐ€ ์†Œ์œ ํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋งฅ์ฃผ์˜ ์–‘์ž…๋‹ˆ๋‹ค.

์ค‘๊ฐ„์ค‘๊ฐ„ ํŽธ์˜์ ์— ๋“ค๋ ค ์ด ๋งฅ์ฃผ ํ•œ ๋ฐ•์Šค๋ฅผ ์ฑ„์šธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ตœ๋Œ€ ๋งฅ์ฃผ ํ•œ ๋ฐ•์Šค๋ฅผ ์†Œ์œ ํ•  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์—

50*20(1๋ฐ•์Šค) ์ฆ‰, ๋‹ค๋ฅธ ์ง€์ ์œผ๋กœ ์ด๋™ํ•  ๋•Œ ๊ฑฐ๋ฆฌ๊ฐ€ 1,000๋ฏธํ„ฐ ์ดํ•˜์ผ ๋•Œ๋งŒ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

๊ทธ๋ฆฌ๊ณ  ์—ฌ๊ธฐ์„œ ๊ฑฐ๋ฆฌ๋Š” x,y์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ ๋‘ ์ขŒํ‘œ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋Š” x ์ขŒํ‘œ์˜ ์ฐจ์ด + y ์ขŒํ‘œ์˜ ์ฐจ์ด์ž…๋‹ˆ๋‹ค.

๊ฐ ์ฃผ์–ด์ง€๋Š” ์ขŒํ‘œ๋“ค์„ ์ €์žฅํ•˜๊ณ 

์ œ์ผ ์ฒ˜์Œ ์ฃผ์–ด์ง€๋Š” ์ƒ๊ทผ์ด๋„ค ์ง‘ ๋ถ€ํ„ฐ

๋งˆ์ง€๋ง‰์— ์ฃผ์–ด์ง„ ํŽœํƒ€ํฌํŠธ ๋ฝ ํŽ˜์Šคํ‹ฐ๋ฐœ ์ขŒํ‘œ๊นŒ์ง€

๋งฅ์ฃผ๊ฐ€ ๋ชจ์ž๋ฅด์ง€ ์•Š๊ฒŒ ๊ฐˆ ์ˆ˜ ์žˆ๋Š”์ง€๋ฅผ ํ™•์ธํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

bfsํƒ์ƒ‰์„ ํ†ตํ•ด ํ’€์ด๊ฐ€ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. bfs ํƒ์ƒ‰์„ ํ†ตํ•ด

1,000 ๋ฏธํ„ฐ ์ดํ•˜์˜ ๊ฑฐ๋ฆฌ์— ์žˆ๋Š” ์ง€์ ์„ ๊ฐˆ ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๊ณ 

์ตœ์ข…์ ์œผ๋กœ ๋งฅ์ฃผ๊ฐ€ ๋ชจ์ž๋ฅด์ง€ ์•Š๊ฒŒ ํŽœํƒ€ํฌํŠธ ๋ฝ ํŽ˜์Šคํ‹ฐ๋ฒŒ์— ๋„์ฐฉ ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธ์ด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

๐Ÿ’ป ์ฝ”๋“œ


package problem.bfsdfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main_9205 {
    static StringBuilder sb = new StringBuilder();
    static final int INF = 10000;
    static boolean[] visited;
    static int position[][];
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc=0; tc<t; tc++){
            n = Integer.parseInt(br.readLine());
            position = new int[n+2][2];
            visited = new boolean[n+2];
            for(int i=0; i<position.length; i++){
                Arrays.fill(position[i],INF);
            }
            for(int i=0; i<n+2; i++){
                String temp[] = br.readLine().split( " ");
                position[i][0] = Integer.parseInt(temp[0]);
                position[i][1] = Integer.parseInt(temp[1]);
            }
            bfs(0,n+1);
        }
        System.out.print(sb.toString());
        br.close();
    }

    private static void bfs(int start,int end){
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);
        while (!queue.isEmpty()){
            int current = queue.poll();
            int x = position[current][0];
            int y = position[current][1];
            if(current == end){
                sb.append("happy\n");
                return;
            }
            for(int i=1; i<n+2; i++){
                if( !visited[i] && ( Math.abs(x-position[i][0]) + Math.abs(y-position[i][1]) <= 1000) ){
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }
        sb.append("sad\n");
    }
}


Written on April 10, 2021