문제

문제 설명

고대 문명 유적 탐사
문제 설명은 이걸로 대체 하려고 한다... 귀찮아서 그런거 아님.

풀기 전 했던 생각

1. 브루트 포스로 싹다 찾아보자.
2. 배열을 직접 회전시키지 말고, 3X3짜리 배열을 1차원으로 만들고 인덱스를 옮겨가며 회전 시키자. (직접 돌리면 헷갈릴 것 같아서..)
3. 90도 회전 함수를 여러번 사용하자.
4. 최적화는 나중에 생각하자.
5. 기능을 엄청 세분화 하자.

풀이

주요 메서드

문제에 나온 기능이 아닌 문제를 풀기 위한 기능을 세분화 함.

• 전체적인 풀이 순서
  1. 중심좌표 찍기
  2. 주변 칸에 대한 배열 수집
  3. 회전
  4. 탐색
  5. 가져갈 수 있는 유물 가져가고
  6. 채워 넣기
     a. 채워 넣은 후 가져갈 수 있는 유물이 더 있는지 확인
  7. 마지막 칸까지 반복
  8. 답 카운트
  9. 1~8까지 k만큼 반복 (탈출 할 수 있음 하고)
     요런 느낌이다.

find()

static void find() {
	for(int i = 1; i < 4; i++) {
		for(int j = 1; j < 4; j++) {
			setArr(i, j);
			
			int dir = 0;
			while(dir++ < 3) {
				rotate(i, j);
				search(i, j, dir);
			}
			rotate(i, j); // 원상복구용
		}
	}
}

탐색하는 메서드.
5X5 배열 중 내부의 3X3을 칸 하나를 중심으로 잡는다.
그리고 setArr(i, j)메서드로 주변 칸에 대한 정보를 1차원 배열에 담고,
while문 3번을 돌면서 회전 및 bfs탐색을 진행한다.

search(int row, int col, int dir)

static void search(int row, int col, int dir) {
	subBag = new ArrayList<>();
	
	boolean[][] visited = new boolean[5][5];
	for(int i = 0; i < 5; i++) {
		for(int j = 0; j < 5; j++) {
			bfs(i, j, visited);
		}
	}
	
	if(shouldChange(row, col, dir)) change(row, col, dir);
}

bfs돌면서 담을 수 있는 유물을 subBag에 담고
finalBag(최대로 얻을 수 있는 유물)과 비교해서 갱신

process()

static void process() {
	finalBag = new ArrayList<>();
	find();
	
	boolean first = true;
	
	while(!finalBag.isEmpty()) {
		ans += finalBag.size();
		
		Collections.sort(finalBag, (o1, o2) -> {
			if(o1[1] == o2[1]) return Integer.compare(o2[0], o1[0]);
			return Integer.compare(o1[1], o2[1]);
		});
		
		if(first) {
			setArr(record.position[0], record.position[1]);
			setAnswer();
			first = false;
		}
		
		fill();
		
		reSearch();
	}
}

문제를 풀기 위한 수행 함수.
매 턴마다 finalBag을 초기화 해주고, 탐색 -> 채우기를 반복함.
finalBag에는 유물이 있었던 좌표가 저장되어 있고, 좀 더 편하게 채우기 위해 정렬함.

전체 코드

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

public class Main_고대문명유적탐사 {
	static int k;
	static int m;
	static int[][] map;
	static Queue<Integer> numbers;
	
	static int[] rows8 = {-1, -1, -1, 0, 1, 1, 1, 0};
	static int[] cols8 = {-1, 0, 1, 1, 1, 0, -1, -1};
	static int[] rows4 = {-1, 1, 0, 0};
	static int[] cols4 = {0, 0, -1, 1};
	
	static int[] rotationArr;
	static int index;
	static int ans;
	
	static List<int[]> finalBag;
	static List<int[]> subBag;
	
	static class Record {
		int[] position = new int[2];
		int dir;
		
		public Record(int[] position, int dir) {
			this.position[0] = position[0];
			this.position[1] = position[1];
			this.dir = dir;
		}
	}
	
	static Record record = new Record(new int[] {-1, -1}, -1);
	public static void main(String[] agrs) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		input(br, st);
		
		while(k-- > 0) {
			ans = 0;
			process();
			
			if(ans == 0) break;
			
			sb.append(ans + " ");
		}
		
		System.out.println(sb);
	}
	
	static void input(BufferedReader br, StringTokenizer st) throws Exception {
		k = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[5][5];
		numbers = new ArrayDeque<>();
		rotationArr = new int[8];
		index = 0;
		ans = 0;
		
		for(int i = 0; i < 5; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < 5; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < m; i++) {
			numbers.offer(Integer.parseInt(st.nextToken()));			
		}
	}
	
	static void process() {
		finalBag = new ArrayList<>();
		find();
		
		boolean first = true;
		
		while(!finalBag.isEmpty()) {
			ans += finalBag.size();
			
			Collections.sort(finalBag, (o1, o2) -> {
				if(o1[1] == o2[1]) return Integer.compare(o2[0], o1[0]);
				return Integer.compare(o1[1], o2[1]);
			});
			
			if(first) {
				setArr(record.position[0], record.position[1]);
				setAnswer();
				first = false;
			}
			
			fill();
			
			reSearch();
		}
	}
	
	static void find() {
		for(int i = 1; i < 4; i++) {
			for(int j = 1; j < 4; j++) {
				setArr(i, j);
				
				int dir = 0;
				while(dir++ < 3) {
					rotate(i, j);
					search(i, j, dir);
				}
				rotate(i, j); // 원상복구용
			}
		}
	}
	
 	static void setArr(int row, int col) {
		for(int i = 0; i < 8; i++) {
			rotationArr[i] = map[row + rows8[i]][col + cols8[i]];
		}
	}
	
	static void setMap(int row, int col) {
		for(int i = 0; i < 8; i++) {
			map[row + rows8[i]][col + cols8[i]] = rotationArr[(index + i) % 8];
		}
	}
	
	static void rotate(int row, int col) { // 90도 회전시키는 함수
		index += 6;
		
		setMap(row, col);
	}
	
	static void search(int row, int col, int dir) {
		subBag = new ArrayList<>();
		
		boolean[][] visited = new boolean[5][5];
		for(int i = 0; i < 5; i++) {
			for(int j = 0; j < 5; j++) {
				bfs(i, j, visited);
			}
		}
		
		if(shouldChange(row, col, dir)) change(row, col, dir);
	}
	
	static void reSearch() {
		subBag = new ArrayList<>();
		
		boolean[][] visited = new boolean[5][5];
		for(int i = 0; i < 5; i++) {
			for(int j = 0; j < 5; j++) {
				bfs(i, j, visited);
			}
		}
		
		finalBag = new ArrayList<>();
		putIn(subBag, finalBag);
	}
	
	static void bfs(int row, int col, boolean[][] visited) {
		Queue<int[]> q = new ArrayDeque<>();
		q.offer(new int[] {row, col});
		
		int target = map[row][col];
		
		visited[row][col] = true;
		
		List<int[]> list = new ArrayList<>();
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			int r = cur[0];
			int c = cur[1];
			
			if(target == map[r][c]) list.add(new int[] {r, c});
			
			for(int i = 0; i < 4; i++) {
				int dr = r + rows4[i];
				int dc = c + cols4[i];
				
				if(isRange(dr, dc) && target == map[dr][dc] && !visited[dr][dc]) {
					q.offer(new int[] {dr, dc});
					visited[dr][dc] = true;
				}
			}
		}
		
		if(list.size() >= 3) putIn(list, subBag);
	}
	
	static boolean shouldChange(int row, int col, int dir) {
		if (finalBag.size() < subBag.size()) {
	        return true;
	    }
	    
	    if (finalBag.size() == subBag.size()) {
	        if (record.dir == dir) {
	            if (record.position[1] == col) {
	                return record.position[0] > row;
	            }
	            return record.position[1] > col;
	        }
	        return record.dir > dir;
	    }

	    return false;
	}
	
	static void change(int row, int col, int dir) {
		record.position[0] = row;
		record.position[1] = col;
		record.dir = dir;
		
		finalBag = new ArrayList<>();
		putIn(subBag, finalBag);
	}
	
 	static void putIn(List<int[]> from, List<int[]> to) {
		for(int[] pos : from) to.add(new int[] {pos[0], pos[1]});
	}
	
 	static void setAnswer() {
 		int row = record.position[0];
 		int col = record.position[1];
 		int dir = record.dir;
 		
 		for(int i = 0; i < 8; i++) {
			map[row + rows8[i]][col + cols8[i]] = rotationArr[(dir * 6 + i) % 8];
		}
 	}
 	
	static void fill() {
		for(int[] pos : finalBag) {
			int row = pos[0];
			int col = pos[1];
			
			map[row][col] = numbers.poll();
		}
	}

	static boolean isRange(int dr, int dc) {
		return dr >= 0 && dc >= 0 && dr < 5 && dc < 5;
	}
}

결과

한 번 틀렸는데, 문제에 대한 최대의 조건(?)을 제대로 읽지도 않고 풀었기 때문이다...
꼭, 꼭, 꼭, 문제를 꼼꼼하게 읽고 넘어가자.