글 읽기 - 57 퍼센트에서 틀렸습니다 뜨는데 예외 상황좀 알려주세요 ㅜㅜ

dut0817 6년 전 0

bfs로 구현하였습니다.

방문되지 않은 노드는 큐에 넣고, time도 넣고 visited도 넣어 주었습니다. (저는 visited배열에 몇가지 경우로 올 수 있는지 ? 를 담았습니다. 예를 들어 1*2 = 2, 1+1 = 2 -> 같은 타임으로 2에 도착할 수 있어서 visited배열에 2라고 저장해주었습니다.)

그리고 만약 방문 되었던 노드라면 그 노드의 time값과 현재 time + 1(앞으로 저장될 값)이 같으면 visited배열을 증가시켜 주었습니다.(즉, 같은 시간에 같은 노드까지 도착할 수 있는 경우 증가)

그리고 만약 방문 되었던 노드중 그노드의 time값보다 작은 경우라면 큐에 추가해주고, visited배열을 1로 바꿔주고 time을 저장해주었습니다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int subin = scan.nextInt();
		int sister = scan.nextInt();
		ArrayList<int[]> queue = new ArrayList<>();
		int temp = subin;
		int[] map = new int[100001];
		int cnt = 0;
		int min = 1000000;
		int[] visited = new int[100001];
		queue.add(new int[] {subin, 0});
		visited[subin] = 1;
		if(subin > sister) {
			System.out.println(subin - sister);
			System.out.println(1);
			return;
		} else if(subin == sister) {
			System.out.println(0);
			System.out.println(1);
			return;
		}
		
		while(queue.size() > 0) {
			int index = queue.get(0)[0];
			int time = queue.get(0)[1];
			queue.remove(0);
			
			if(index == sister) {
				if(min > time) {
					min = time;
				} else if(min == time) {

				}
			}
			
			if(index - 1 >= 0) {
				if(visited[index - 1] == 0) {
					visited[index - 1] = visited[index];
					map[index - 1] = time + 1;
					queue.add(new int[] {index - 1, time + 1});
				} else {
					if(map[index - 1] == time+1) {
						visited[index - 1]++;
					} else if(map[index - 1] > time + 1) {
						visited[index - 1] = 1;
						map[index - 1] = time + 1;
						queue.add(new int[] {index - 1,  time + 1});
					}
				} 
			}
			if(index + 1 <= 100000) {
				if(visited[index + 1] == 0) {
					visited[index + 1] = visited[index];
					map[index + 1] = time + 1;
					queue.add(new int[] {index + 1, time + 1});
				} else {
					if(map[index + 1] == time+1) {
						visited[index + 1]++;
					} else if(map[index + 1] > time + 1) {
						visited[index + 1] = 1;
						map[index + 1] = time + 1;
						queue.add(new int[] {index + 1,  time + 1});
					}
				} 
			}
			if(index * 2 <= 100000) {
				if(visited[index * 2] == 0) {
					visited[index * 2] = visited[index];
					map[index * 2] = time + 1;
					queue.add(new int[] {index * 2, time + 1});
				} else {
					if(map[index * 2] == time+1) {
						visited[index * 2]++;
					} else if(map[index * 2] > time + 1) {
						visited[index * 2] = 1;
						map[index * 2] = time + 1;
						queue.add(new int[] {index * 2,  time + 1});
					}
				} 
			}
				
		}
		System.out.println(min);
		System.out.println(visited[sister]);
		
	}
}

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

문제

문제

출처

ICPC

57 퍼센트에서 틀렸습니다 뜨는데 예외 상황좀 알려주세요 ㅜㅜ

dut0817 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말