BOJ. 19237번. 어른상어

 

이번 문제는 특별한 알고리즘 개념 없이 단순한 구현 문제였는데 두시간이 넘게 걸렸다.

1. 각 상어의 위치와 상태(방향 등) 값을 따로 저장하고, 상어 구분을 위한 배열, 구분된 상어의 냄새를 위한 배열
    두가지를 사용한다.
2. 시간의 흐름에 따라 상어를 움직이는데, 우선순위를 유의해서 상어의 옮길 위치를 업데이트 한다.
3. 옮기기 전에 기존의 냄새를 1씩 날리고, 옮긴 위치의 냄새는 처음 냄새 값인 k를 넣는다.
4. 실수에 유의한다.

차분하게 푸는 습관이 필요하다고 느꼈다. 꼭 채워넣고 싶은 점은 다음 두가지였다.

1. 구현문제에서 항상 그렇듯, 시간이 지날때 마다 지우고 빼는 등, 시점에 따른 컨트롤이 아직 미숙하다.
2. 로직은 항상 괜찮게 짜는 듯 한데, 잔실수가 많다. (Expert 프로님께서 반드시 고치라고 하신 부분;;;

리스트가 있을 때, 삭제하고 싶은 인덱스를 미리 지정해 놓았다고 하자. 그리고 해당 인덱스를 지우기 위한 방법으로,

for(int index : list{
	list.remove(index);
}

와 같은 짓을 하는 똥멍청이는 나밖에 없을 듯 하다. 

www.acmicpc.net/problem/19237

19237번: 어른 상어

 

package week8;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Day7BOJ19237 {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	
	static int n,m,k; // 크기,상어수,냄새소멸
	static int time;
	static int[][] map,smell;
	static int[][][] priority;
//	                 방향: 상 하  좌 우 (1,2,3,4) 
	static int[] dy = {0,-1, 1, 0, 0};
	static int[] dx = {0, 0, 0,-1, 1};
	static ArrayList<Shark> list = new ArrayList<Shark>();
	static class Shark implements Comparable<Shark>{
		int num,y,x,d; 
		public Shark(int num, int y, int x, int d) {
			this.num = num;
			this.y = y;
			this.x = x;
			this.d = d;
		}
		@Override
		public int compareTo(Shark o) {
			return (this.num-o.num);
		}
	}

	private static boolean checkBound(int y, int x) {
		return (y>=0 && y<n && x>=0 && x<n) ? true : false;
	}
	
	private static void sharkMove() {
		for(int i=0; i<list.size(); i++) { // list중 상어 1마리에 대해
			boolean flag=true;
			Shark s = list.get(i);
			int on = s.num;
			int oy = s.y;
			int ox = s.x;
			int od = s.d;
//			i번 상어 다음 좌표 결정
			for(int d=1; d<=4; d++) {
				// 방향에 따라 우선순위 달라짐
				int ny = oy + dy[priority[on][od][d]];
				int nx = ox + dx[priority[on][od][d]];
				// 우선순위에 따른 빈칸이 있는 경우
				if(checkBound(ny,nx) && map[ny][nx]==0) {
					// 상어 좌표,방향 일단 가능한 쪽으로 갱신
					list.get(i).y = ny;
					list.get(i).x = nx;
					list.get(i).d = priority[on][od][d];
					flag=false;
					break;
				}
			}
			if(flag) { // 빈칸이 없었던 경우에는 주변중 이전 자신 냄새로 돌아간다.
				for(int d=1; d<=4; d++) {
					int ny = oy + dy[priority[on][od][d]];
					int nx = ox + dx[priority[on][od][d]];
					if(checkBound(ny,nx) && map[ny][nx]==on) {
						list.get(i).y = ny;
						list.get(i).x = nx;
						list.get(i).d = priority[on][od][d];
						break;
					}
				}
			}
		}
//		상어들의 다음 상태 결정되고 나면, smell을 하나씩 감소
		eraseSmell();
//		그 후 상어들의 상태를 map,smell에 반영
		ArrayList<Integer> target = new ArrayList<Integer>();
		for(int i=0; i<list.size(); i++) {
			Shark s = list.get(i);
			if(map[s.y][s.x]==0 || map[s.y][s.x]==s.num) { // 새 자리 or 자기 냄새인 경우
				map[s.y][s.x] = s.num;
				smell[s.y][s.x] = k;
			}else { // 0이여야 하는데 다른 상어가 있는 경우
				target.add(i); // 기존에 상어가 있다면 무조건 짐
			}
		}
		int gap=0;
		for(int t : target) {
			list.remove(t+(gap--)); // 원하는 인덱스 한번에 지울때 주의!
		}
	}
	
	private static void eraseSmell() {
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(smell[i][j]!=0) {
					smell[i][j]--; // 냄새 잔여시간 1씩 줄임
					if(smell[i][j]==0) {
						map[i][j]=0; // 냄새 0이되는 상어흔적은 지움
					}
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
//		data Input
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		smell = new int[n][n];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j]!=0) {
					list.add(new Shark(map[i][j],i,j,0)); // 상어 임시리스트에 방향없는 상태로 추가
					smell[i][j] = k; // 상어 냄새 초기화
				}
			}
		}
		Collections.sort(list); // 상어 번호로 정렬
		// 상어 리스트에 상어상태 추가
		st = new StringTokenizer(br.readLine());
		for(int s=0; s<m; s++) {
			list.get(s).d = Integer.parseInt(st.nextToken());
		}
		priority = new int[m+1][5][5]; // a번 상어 기존 b방향에서의 방향우선순위 4개
		for(int a=1; a<=m; a++) {
			for(int b=1; b<=4; b++) {
				st = new StringTokenizer(br.readLine());
				for(int c=1; c<=4; c++) {
					priority[a][b][c] = Integer.parseInt(st.nextToken());
				}
			}
		}
		
//		solution
		while(true) {
			if(list.size()==1 || time==1001) break; // 종료조건
			sharkMove();   // 상어 움직이고
			time++;
		}
		
		time = (time==1001) ? -1 : time;
		System.out.println(time);
	}

}