글 읽기 - BFS 이용해서 풀었는데 계속 오답입니다. 너무 답답합니다. 도와주세요ㅠㅠ

jeongks94 3년 전 0

BFS 이용해서 풀었는데 7%에서 계속 오답이네요ㅠㅠ

어느 로직에서 문제가 있는지 조언 부탁드립니다. 너무 답답하네요

package BFS;

import java.util.*;
import java.io.*;

public class N9205 {

	static class Dot{
		int x,y,cnt;
		public Dot(int x,int y) {
			this.x = x;
			this.y = y;
		}
	}
	static boolean [] visited;
	static boolean flag;
	static int sx,sy,rx,ry;
	static int n;
	static ArrayList<Dot> arrlist;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int t = Integer.parseInt(br.readLine());
		while(t-->0) {
			flag = false;
			arrlist = new ArrayList<>();
			n = Integer.parseInt(br.readLine()); //맥주를 파는 편의점의 수
			visited = new boolean [n];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			sx = Integer.parseInt(st.nextToken());
			sy = Integer.parseInt(st.nextToken());
			
			for(int i=0;i<n;i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				arrlist.add(new Dot(x,y));
			}
			
			st = new StringTokenizer(br.readLine());
			rx = Integer.parseInt(st.nextToken());
			ry = Integer.parseInt(st.nextToken());
			
			int dist = Math.abs(sx-rx) + Math.abs(sy-ry);
			
			//처음에 한방에 갈 수 있는 거리면
			if(dist<=1000) {
				bw.append("happy\n");
			}
			else {
				bfs();
				if(!flag)
					bw.append("sad\n");
				else
					bw.append("happy\n");
			}
		}
		bw.flush();
		bw.close();
	}
	
	public static void bfs() {
		//현재 위치를 나타내는 객체
		Queue<Dot> queue = new LinkedList<>();
		queue.add(new Dot(sx,sy)); //시작점 집어넣고
		int x = sx;
		int y = sy;
		
		//시작점
		
		while(!queue.isEmpty()) {
			Dot dot = queue.poll();
			
			//현재 점에서 다음 마지막 점까지 1000이하로 가능하다면
			if(check(dot.x,dot.y,rx,ry)) {
				flag = true;
				return;
			}
			
			//그냥 해야하는건
			for(int i=0;i<arrlist.size();i++) {
				if(!visited[i]) {
					visited[i] = true;
					Dot tmp = arrlist.get(i);
					int nx = tmp.x;
					int ny = tmp.y;
					//다음점까지 1000이하라면
					if(check(x,y,nx,ny)) {
						x = nx;
						y = ny;
						queue.add(new Dot(nx,ny));
					}
					else
						continue;
				}
			}
		}
	}
	
		
	//범위를 체크
	public static boolean check(int x,int y,int x2,int y2) {
		if(Math.abs(x-x2)+Math.abs(y-y2)<=1000)
			return true;
		else
			return false;
	}
}

qjatn1009 3년 전 0

91번 라인에 check(x,y,nx,ny)가 아니라 check(dot.x, dot.y, nx, ny)가 아닐까용?..

x와 y는 queue에 들어간 마지막 값이 일꺼 같네요

tiro25 3년 전 0

86줄을 91번째줄 if문 안에 넣어보세요

바로 방문여부를 갱신하는게 아니라 거리가 1000이하일때만 방문가능해서 visited 갱신하는 부분을 if문 안에 넣어줘야될것 같아요

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

문제

문제

출처

ICPC

BFS 이용해서 풀었는데 계속 오답입니다. 너무 답답합니다. 도와주세요ㅠㅠ

jeongks94 3년 전 0

qjatn1009 3년 전 0

tiro25 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

﻿BFS 이용해서 풀었는데 계속 오답입니다. 너무 답답합니다. 도와주세요ㅠㅠ

jeongks94 3년 전 0

qjatn1009 3년 전 0

tiro25 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

BFS 이용해서 풀었는데 계속 오답입니다. 너무 답답합니다. 도와주세요ㅠㅠ