글 읽기 - 코드 한번 봐주시면 감사하겠습니다.

hik3562 4년 전 0

틀렸습니다.. 가 되는데

1. 홈에서 편의점 거리 1000 내 있는거 따로 저장하는 Queue

2. 편의점을 다 저장하는 ArrayList

3. 이걸 BFS 로 돌려서 홈에서 시작해서 현재위치를 Queue에 저장되어 있는 편의점 좌표로 계속 갱신,이동할 수 있는 곳이면 Queue에 저장

4. Lock Festival 와 1000 거리 내 있으면 haapy

5. Queue 를 다 봐도 없으면 sad

위 로직으로 구성하였습니다.

조언 부탁드립니다. 감사합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int total;
	static int convience_store;
	static int gx, gy;
	static boolean find = false;
	static ArrayList<int[]> al;
	static int[] visit;
	static class Pair{
		int cx;
		int cy;
		
		Pair(int cx, int cy){
			this.cx = cx;
			this.cy = cy;
		}
	}
	static Queue<Pair> q = new LinkedList<>();
	static void BFS() {

		while(!q.isEmpty()) {
			Pair p = q.poll();
			
			//거리 판단
			if(Math.abs(gx-p.cx)/50+Math.abs(gy-p.cy)/50<=20) {
				find = true;
				break;
			}
			for(int i=0; i<al.size(); i++) {
				//현재위치에서 편의점 위치 뺀게 갈 수 있는지 확인하는 코
					if(al.get(i)[0] == p.cx && al.get(i)[1] ==p.cy) continue;
					if(Math.abs(p.cx-al.get(i)[0])/50+Math.abs(p.cy-al.get(i)[1])/50>20 || visit[i] != 0) continue;
					//방문한적이 있거나, 거리내에 들어갈 수 있는지 
					visit[i] = 1;
					//다음 편의점
					q.add(new Pair(al.get(i)[0],al.get(i)[1]));
			}
		}
	}
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		total = Integer.parseInt(br.readLine());
		
		
		for(int i=0; i<total; i++) {
			int convience_cnt = Integer.parseInt(br.readLine()); //편의점 개수
			StringTokenizer st = new StringTokenizer(br.readLine());
			int hx = Integer.parseInt(st.nextToken());
			int hy = Integer.parseInt(st.nextToken());
			
			
			q.add(new Pair(hx,hy));
			al = new ArrayList<>();
			
			for(int j=0; j<convience_cnt; j++) {
				st = new StringTokenizer(br.readLine());
				int cx = Integer.parseInt(st.nextToken());
				int cy = Integer.parseInt(st.nextToken());
				if(Math.abs(hx-cx)/50+Math.abs(hy-cy)/50<=20) q.add(new Pair(cx, cy));			
				al.add(new int[] {cx,cy}); //저장 
				
				//편의점을 큐에 다 넣고 
			}
			
			
			st = new StringTokenizer(br.readLine());
			gx = Integer.parseInt(st.nextToken());
			gy = Integer.parseInt(st.nextToken());
				
			visit = new int[al.size()];
			find = false;
			BFS();
			if(find == false) {
				System.out.println("sad");
			}else {
				System.out.println("happy");
			}
		}//end of for loop
	}
}

slah007 4년 전 2

우선, '/' 연산을 하고 나면 나머지를 버리기 때문에, 거리 판단에서 로직이 잘못되었습니다.

input

2
2
0 0
1000 0
1000 1000
2000 1001
2
0 0
1000 0
2000 1000
2000 2000

output

happy (sad가 나와야 함)

sad

TMI: 이 문제는 BFS 말고도 해결이 가능해요!

단 for문 3개만으로 최단경로를 찾아낼 수 있는 floyd-warshall 알고리즘을 적용하면 됩니다.

1. 집, 편의점들, 페스티벌 장소를 정점으로 보고, 서로 거리를 계산해서 20*50=1000블럭 이하이면 갈 수 있다(1), 아니면 없다(INF)으로 표시한다.

2. floyd-warshall 알고리즘으로 모든 정점쌍들 사이 최단경로를 찾는다.

3. 만약 집에서 페스티벌 장소까지 최단경로(<INF)가 존재하면 happy, 존재 안하면 sad를 출력한다.

hik3562 4년 전 0

우와 이런 자세한 설명까지... 감사합니다. 😊

hik3562 4년 전 0

AC 처리 되었는데 다음 요소를 고려 해야 합니다.

앞서 지적 해주신 float 부분 그리고 Queue 를 전역으로 박아놨습니다.

수정 하면 AC 됍니다.

👍

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코드 한번 봐주시면 감사하겠습니다.

hik3562 4년 전 0

slah007 4년 전 2

hik3562 4년 전 0

hik3562 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말