글 읽기 - 이 코드 시간 복잡도 O(V+E) 가 맞나요?

hik3562 4년 전 0

맞다면 시간 복잡도를 더 떨어뜨릴 수 있는,

좀더 최적화 시킬 수 있는 방법이 있을까요?

실행시간은 224ms 였습니다.

봐주시는 모든분들 감사합니다.

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

public class Main {

	private static int N;
	private static int ni, nj;
	private static int ans;
	private static int[][] map;
	private static int[][] visit;
	private static int[] dx = { -1, 1, 0, 0 };
	private static int[] dy = { 0, 0, -1, 1 };

	private static class Pair {
		int x;
		int y;
		int size;
		int eat;
		int time;

		Pair(int x, int y, int size, int eat, int time) {
			this.x = x;
			this.y = y;
			this.size = size;
			this.eat = eat;
			this.time = time;
		}
	}

	private static class Pair2 implements Comparable<Pair2> {
		int x;
		int y;
		int dist;

		Pair2(int x, int y, int dist) {
			this.x = x;
			this.y = y;
			this.dist = dist;
		}

		@Override
		public int compareTo(Pair2 o) {
			// TODO Auto-generated method stub
			if (this.dist == o.dist) {
				if (this.x == o.x)
					return this.y - o.y; // 가장 왼쪽에 있고
				return this.x - o.x; // 가장 위쪽에 있고
			}
			return this.dist - o.dist; // 거리가 가깝고
		}

	}

	private static int abs(int x, int y) {
		if (x > y)
			return x - y;
		else
			return y - x;
	}

	private static void BFS(int nn) {
		int x = nn / N;
		int y = nn % N;
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(x, y, 2, 0, 0)); // x좌표, y좌표, 사이즈, 먹은수, 시간
		while (!q.isEmpty()) {
			Pair babyShark = q.remove();
			boolean find = false;
			visit = new int[N][N];
			Queue<int[]> q2 = new LinkedList<>();
			q2.add(new int[] { babyShark.x, babyShark.y, babyShark.size, babyShark.eat, babyShark.time });
			ArrayList<Pair2> a = new ArrayList<>();
			k: while (!q2.isEmpty()) {
				int[] m = q2.remove();
				// m[0] : x, m[1] : y, m[2] : size, m[3] : 먹은개수, m[4] : 시간
				if (m[2] > map[m[0]][m[1]] && map[m[0]][m[1]] != 0) {
					a.add(new Pair2(m[0], m[1], m[4]));
					find = true;
				}
				visit[m[0]][m[1]] = 1;
				for (int i = 0; i < 4; i++) {
					int ddx = m[0] + dx[i];
					int ddy = m[1] + dy[i];
					if (ddx < 0 || ddx >= N || ddy < 0 || ddy >= N)
						continue;
					if (visit[ddx][ddy] == 0 && babyShark.size >= map[ddx][ddy]) {
						q2.add(new int[] { ddx, ddy, m[2], m[3], m[4] + 1 }); // 시간 증가
						visit[ddx][ddy] = 1;
					}
				}
			} // end of while loop

			if (find == true) {
				Collections.sort(a);
				if (babyShark.size == babyShark.eat + 1) // 자기 등치만큼 먹었을때 => 사이즈 증가
					q.add(new Pair(a.get(0).x, a.get(0).y, babyShark.size + 1, 0, a.get(0).dist));
				else if (babyShark.size != babyShark.eat) // 자기 등치만큼 못먹었을때 => 사이즈 증가 x, 먹은 물고기가 하나 증가
					q.add(new Pair(a.get(0).x, a.get(0).y, babyShark.size, babyShark.eat + 1, a.get(0).dist));
				map[a.get(0).x][a.get(0).y] = 0;
				ans = a.get(0).dist;
				Arrays.toString(map);
			}
		}

	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 9) {
					map[i][j] = 0;
					ni = i;
					nj = j;
				}
			}
		} // end of for loop
			// 아기상어 위치, ni, nj

		BFS(ni * N + nj);
		System.out.println(ans);

	}

}

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

문제

문제

출처

ICPC

이 코드 시간 복잡도 O(V+E) 가 맞나요?

hik3562 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말