글 읽기 - 기존소스에서 시간초과나서 그냥 원초적으로 짯는데 풀렸습니다.

redbin0471 4년 전 1

기존에는 P,K에 있는 높이를 입력받을때 모두조사하야서 가장 큰값과 작은값을 구해두고 left right를 구해두고 이중포문으로

범위를 구해나가는 방식을 선택했습니다.

그런데 시간초과가나서 원초적으로 left = 0 right =0 부터 시작해서 갈수없으면 right를 증가시키고 갈수있으면 left를 줄여서 범위를 줄여나가는 방식은 통과했습니다..

이중포문이 더느린 이유가 있을까요 ??

///////////기존소스
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static int N;
	static int weight[][];
	static char Map[][];

	public static class XY {
		int y;
		int x;

		public XY(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

	}

	static int dy[] = { 0, 0, 1, 1, 1, -1, -1, -1 };
	static int dx[] = { -1, 1, 0, 1, -1, 0, 1, -1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st;

		weight = new int[N][N];
		Map = new char[N][N];
		XY start = null;
		for (int i = 0; i < N; i++) {
			Map[i] = br.readLine().toCharArray();
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				weight[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// min Max 찾기

		int MinValue = Integer.MAX_VALUE;
		int MaxValue = Integer.MIN_VALUE;
		int pCnt = -1;
		TreeSet<Integer> set = new TreeSet<Integer>();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (Map[i][j] == 'P' || Map[i][j] == 'K') {
					pCnt++;
					MinValue = Math.min(MinValue, weight[i][j]);
					MaxValue = Math.max(MaxValue, weight[i][j]);
					if (Map[i][j] == 'P') {
						start = new XY(i, j);
					}
				}
				set.add(weight[i][j]);
			}
		}

		Iterator<Integer> iter = set.iterator();
		int Look[] = new int[set.size()];
		for (int i = 0; i < set.size(); i++) {
			Look[i] = iter.next();
//			System.out.print(Look[i]+" ");
		}
//		System.out.println();

		int left = 0;
		int right = 0;

		for (int i = 0; i < Look.length; i++) {
			if (Look[i] == MinValue) {
				left = i;
				break;

			}
		}

		for (int i = 0; i < Look.length; i++) {
			if (Look[i] == MaxValue) {
				right = i;
				break;

			}
		}

		boolean Escape = false;
		int result = Integer.MAX_VALUE;
		int checkCnt = 0;
		for (int i = left; i >= 0; i--) {
			MinValue = Look[i];
			if(result<= MaxValue - Look[right])break;;
			for (int j = right; j < Look.length; j++) {
				MaxValue = Look[j];
//				System.out.println(MinValue + " " + MaxValue);
				if(result<= MaxValue - MinValue)break;
				boolean check[][] = new boolean[N][N];

//				for (int y = 0; y < N; y++) {
//					for (int x = 0; x < N; x++) {
//						if (weight[y][x] >= MinValue && weight[y][x] <= MaxValue) {
//							check[y][x] = true;
//						}
//					}
//				}

				// BFS로 확인하기
				Queue<XY> q = new LinkedList<>();
				q.add(start);
				check[start.y][start.x] = true;
				int cnt = 0;
				while (!q.isEmpty()) {
					XY tmp = q.poll();
					for (int d = 0; d < 8; d++) {
						int ny = tmp.y + dy[d];
						int nx = tmp.x + dx[d];

						if (ny < 0 || nx < 0 || ny >= N || nx >= N)
							continue;
						if (check[ny][nx] == true)
							continue;
						if(weight[ny][nx] <MinValue || weight[ny][nx]>MaxValue) continue;
						
						if (Map[ny][nx] == 'K')
							cnt++;
						check[ny][nx] = true;
						q.add(new XY(ny, nx));
					}
					if (cnt == pCnt) {
						checkCnt++;
//						System.out.println(MinValue + " " + MaxValue);
//						System.out.println("cnt++");
						
						result =Math.min(result,MaxValue - MinValue);
//						if(checkCnt==3) {
//							Escape = true;
//						}
						break;
					}
				}
				if(Escape) break;
			}
			if(Escape) break;
		}

		System.out.println(result);

	}
}


////////
/////////
////////
///////

///변경후 소스

package com.ssay.algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeSet;

import com.ssay.algo.B2842.XY;

public class B2842 {
	static int N;
	static int weight[][];
	static char Map[][];

	public static class XY {
		int y;
		int x;

		public XY(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

	}

	static int dy[] = { 0, 0, 1, 1, 1, -1, -1, -1 };
	static int dx[] = { -1, 1, 0, 1, -1, 0, 1, -1 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st;

		weight = new int[N][N];
		Map = new char[N][N];
		XY start = null;
		int pCnt = 0;
		
		for (int i = 0; i < N; i++) {
			Map[i] = br.readLine().toCharArray();
			for (int j = 0; j < N; j++) {
				if (Map[i][j] == 'K') {
					pCnt++;
					
				}else if (Map[i][j] == 'P') {
					start = new XY(i, j);
				}
				
			}
		}
		
		TreeSet<Integer> set = new TreeSet<Integer>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				weight[i][j] = Integer.parseInt(st.nextToken());
				set.add(weight[i][j]);
			}
		}

		Iterator<Integer> iter = set.iterator();
		int Look[] = new int[set.size()];
		for (int i = 0; i < set.size(); i++) {
			Look[i] = iter.next();
		}
		
		int result = Integer.MAX_VALUE;
		
		int left = 0;
		int right = 0;
		
		while(left<=right && right<set.size()) {
			int checkCnt = 0;

			Queue<XY> q =new LinkedList<>();
			boolean check[][] = new boolean[N][N];
			
			if(weight[start.y][start.x]>=Look[left] &&weight[start.y][start.x]<=Look[right]) {
				q.add(start);
				check[start.y][start.x] = true;
				
			}
			
			while(!q.isEmpty()) {
				XY tmp = q.poll();
				
				for(int d=0;d<8;d++) {
					int ny = tmp.y + dy[d];
					int nx = tmp.x + dx[d];
					if(ny<0||nx<0||ny>=N||nx>=N)continue;
					if(check[ny][nx])continue;
					if(weight[ny][nx]<Look[left]||weight[ny][nx]>Look[right])continue;
					
					if(Map[ny][nx] == 'K') checkCnt++;
					check[ny][nx] = true;
					q.add(new XY(ny,nx));
				}
			}
			if(checkCnt == pCnt) {
				
				result = Math.min(result, Look[right]-Look[left]);
				left++;
			}else {
				right++;
			}
			
			
			
			
			
		}
		
		

		System.out.println(result);

	}
}

chw0501 4년 전 1

기존은 O(N^2) 이고 수정한 코드는 투 포인터 알고리즘으로 O(N)입니다.

매 루프를 돌때 left와 right둘중 하나가 1씩 늘어나는데 left가 N번 증가하면 루프는 무조건 끝이나고

right가 N번 증가해도 루프는 무조건 끝납니다. 따라서 합쳐서 O(N)입니다.

redbin0471 4년 전 0

그렇군요 생각해보니 그렇네요 감사합니다!

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

문제

문제

출처

ICPC

기존소스에서 시간초과나서 그냥 원초적으로 짯는데 풀렸습니다.

redbin0471 4년 전 1

chw0501 4년 전 1

redbin0471 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말