이상한 피라미드 탐험 [SWEA 4112][JAVA][D5][BFS][List]

 

[광고 누르면 오늘의 행운 상승!!]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH&categoryId=AWJHmLraeEwDFAUH&categoryType=CODE

SW Expert Academy

무식하게 풀었다.

1. 참고사항

- 피라미드 모양으로 10001개까지 List를 이어주었다.
- 오른쪽 대각선 아래, 왼쪽 대각선 아래, 오른쪽 3방향을 이으면 다 이어진다.

2. 구현

- 테스트 케이스 마다 리스트를 이으면 시간초과가 발생한다. (이걸 못 깨달아서 8번틀렸다)
- 테스트 케이스 실행 전에 리스트를 만들어서 1000번 재사용한다.
- 오른쪽 대각선 아래는 1,3,6,10 ....의 수열로 이루어져 있고 왼쪽 대각선 아래는 1,2,4,7...의 수열로 이루어져 있다.
- 이 수열들은 증가하는 폭이 일정하므로 규칙을 찾을 수 있었다.
- 규칙에 맞게 모든 리스트를 이어주었다.
- 그후 bfs를 이용하여 최단거리를 찾아내었다.
- 풀리면 푼거지 뭐

package Study6;
import java.io.*;
import java.util.*;

class Player{
	int node, cnt;
	public Player(int node, int cnt) {
		this.node = node;
		this.cnt = cnt;
	}
}
public class 이상한피라미드2 {

	static ArrayList<ArrayList<Integer>> list;
	static int[][] map;
	static int from, to;
	static int N,ans;
	static boolean visit[];
	static Queue<Player> q;
	static boolean flag;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		visit = new boolean[10001];
		list = new ArrayList<>();
		for (int i = 0; i < 10001; i++) {
			list.add(new ArrayList<>());
		}
		
		Link();
		
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to   = Integer.parseInt(st.nextToken());
			
		
			bfs();
			
			System.out.println("#" + tc + " " + ans);
		}
	}
	private static void bfs() {
		q = new LinkedList<>();
		q.add(new Player(from, 0));
		
		visit = new boolean[10001];
		visit[from] = true;
		
		while(!q.isEmpty()) {
			Player player = q.poll();
			
			if(player.node == to) {
				ans = player.cnt;
				return;
			}
			
			for(Integer next : list.get(player.node)) {

				if(next > 10000) continue;
				if(!visit[next]) {
					visit[next] = true;
					q.add(new Player(next,player.cnt+1));
				}
			}
		}
	}
	private static void Link() {
		
		//오른쪽 대각선 아래
		int t = 1;
		int jump = 2;
		while(true) {
			boolean flag = false;
			
			for (int i = 1; i < 10001; i++) {
				if(!visit[i] && (i + jump) < 10001) {
					flag = true;
					visit[i] = true;
					list.get(i).add(i+ jump);
					list.get(i+ jump).add(i);
					i += jump-1;
					jump++;
				}
			}
			jump = 2 + t;
			t++;
			if(!flag) break;
		}
		visit = new boolean[10001];
		//왼쪽 대각선 아래
		t = 1;
		jump = 1;
		while(true) {
			boolean flag = false;
			
			for (int i = 1; i < 10001; i++) {
				if(!visit[i] && (i + jump) < 10001) {
					flag = true;
					visit[i] = true;
					list.get(i).add(i+ jump);
					list.get(i+ jump).add(i);
					i += jump-1;
					jump++;
				}
			}
			jump = 1 + t;
			t++;
			if(!flag) break;
		}
		visit = new boolean[10001];
		//오른쪽
		t = 1;
		jump = 1;
		int idx = 1;
		while(true) {
			boolean flag = false;
			
			for (int i = t; i < 10001; i++) {
				if(!visit[i] && (i + 1) < 10001) {
					flag = true;
					visit[i] = true;
					if(i == jump) break;
					list.get(i).add(i+1);
					list.get(i+1).add(i);
				}
			}
			t+= idx;
			jump += ++idx;
			
			if(!flag) break;
		}
		
	}
}