๐ [๋ฐฑ์ค์๊ณ ๋ฆฌ์ฆ ํ์ด] 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");
}
}