Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 자바입출력
- jquery dom 계층 선택자
- 서로소
- 상속
- 자바스크립트 이벤트중지
- java 내부 클래스
- 자바
- 알고리즘 그래프
- jquery 속성선택자
- char to str
- 자바 순열 코드
- java Collections.sort()
- 자바 재귀 조합
- parseInt()
- 조합 재귀
- inner class
- Interface
- 재귀함수
- jquery 이벤트 처리
- 자바 조합 재귀
- str to char array
- 순열코드
- java lambda
- 순열 재귀
- jquery 필터선택자
- 후위표기
- 자바스크립트 이벤트처리
- 알고리즘
- Java
- 재귀
Archives
- Today
- Total
유블로그
[Java] BOJ 19237 어른상어 본문
[Java] BOJ 19237 어른상어
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class BOJ_19237_어른상어 {
static class Shark {
int x, y, d, no;
int[][] dirOrder = new int[5][4];
public Shark(int x, int y, int no) {
this.x = x;
this.y = y;
this.no = no;
}
}
static class Smell {
int sharkNo, time;
}
static int N, M, k;
static Shark[] sharks;
static Smell[][] smell;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
smell = new Smell[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
smell[i][j] = new Smell();
}
}
sharks = new Shark[M + 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int no = Integer.parseInt(st.nextToken());
if (no == 0)
continue;
sharks[no] = new Shark(i, j, no);
}
}
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= M; i++) {
sharks[i].d = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= 4; j++) { // 1위, 2왼, 3아래, 4오
st = new StringTokenizer(br.readLine());
for (int j2 = 0; j2 < 4; j2++) {
sharks[i].dirOrder[j][j2] = Integer.parseInt(st.nextToken());
}
}
}
System.out.println(solve());
} // main
static int[][] dir = { { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
private static int solve() {
int T = 0;
while (true) {
// 1번 상어만 남았다면 종료
boolean isEnd = true;
for (int i = 2; i <= M; i++) {
Shark shark = sharks[i];
if (shark.no != 0) {
isEnd = false;
break;
}
}
if (isEnd)
break;
// 모든 상어가 자신의 위치에 냄새를 뿌린다.
for (int i = 1; i <= M; i++) {
Shark shark = sharks[i];
if (shark.no == 0)
continue;
smell[shark.x][shark.y].sharkNo = shark.no;
smell[shark.x][shark.y].time = k;
}
// 모든 상어가 이동한다.
for (int i = 1; i <= M; i++) {
Shark shark = sharks[i];
if (shark.no == 0)
continue;
int[] order = shark.dirOrder[shark.d]; // 상어의 방향에 따른 방향우선순위
boolean isFind = false;
for (int j = 0; j < 4; j++) {
int nx = shark.x + dir[order[j]][0];
int ny = shark.y + dir[order[j]][1];
if (!isInBound(nx, ny))
continue;
if (smell[nx][ny].sharkNo == 0) {
shark.x = nx;
shark.y = ny;
shark.d = order[j];
isFind = true;
break;
}
} // j
if (!isFind) { // 다 냄새 있으면 내 냄새중 우선순위 높은 걸로 이동
for (int j = 0; j < 4; j++) {
int nx = shark.x + dir[order[j]][0];
int ny = shark.y + dir[order[j]][1];
if (!isInBound(nx, ny))
continue;
if (smell[nx][ny].sharkNo == shark.no) {
shark.x = nx;
shark.y = ny;
shark.d = order[j];
break;
}
} // j
}
}
// 같은 칸에 있는 상어중 강한 상어만 남기고 다 없앤다.
List<Integer>[][] grid = new ArrayList[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
grid[i][j] = new ArrayList<>();
}
}
for (int i = 1; i <= M; i++) {
Shark shark = sharks[i];
if (shark.no == 0)
continue;
grid[shark.x][shark.y].add(shark.no);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j].size() > 1) {
for (int n = 1; n < grid[i][j].size(); n++) {
sharks[grid[i][j].get(n)].no = 0;
}
}
}
}
// 이동 후 모든 냄새 time 을 줄이는데 time 만료된 냄새 없앤다.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (smell[i][j].sharkNo == 0)
continue;
smell[i][j].time--;
if (smell[i][j].time == 0)
smell[i][j].sharkNo = 0;
}
}
T++;
if(T > 1000) return -1;
} // while
return T;
} // solve
static boolean isInBound(int x, int y) {
if (x < 0 || x >= N || y < 0 || y >= N)
return false;
return true;
}
}
자신의 위치, 방향, 번호, 방향우선순위를 담고 있는 class Shark
상어번호, 시간을 담고 있는 Smell 클래스가 있다.
Smell 을 담고 있는 NxN 배열과
Shark를 담고 있는 길이 M 배열이 있다.
1. while 문 안에서 처음에 1번 상어만 남았다면 종료 시킨다.
2. 모든 상어가 자신의 위치에 냄새를 뿌린다. smell 배열에 shark 순회하면서 해당위치에 넣어준다. 시간은 k.
3. 모든 상어가 이동한다. 상어방향에 따라 우선순위가 다르므로 상어를 순회하면서
현재 방향에 따른 우선순위 순서대로 for 문을 돌려 smell 배열에서 아무 냄새 없는 칸 찾으면 거기로 이동시키고
모든 칸이 냄새있으면 다시 내 우선순위 for문 순회하면서 내 냄새로 간다.
4. NxN List 배열을 만들고 상어순회하면서 그 위치마다 List 배열에 넣는다.
list 배열을 순회하면서 size 가 2이상인 것은 list의 첫번째 인덱스 제외하고 나머지인덱스 shark를 없앤다.
5. smell 배열 순회하면서 모든 time 줄인다. time 이 0 이 되면 sharkNo를 0으로 바꾸어 냄새를 없앴다.
6. 시간을 올린다. 시간이 1000보다 커졌을 때 return -1 한다.
나는 시간이 1000보다 커졌을 때 return -1 하는 부분을 이상한 위치에 줘서 틀렸었다....
'알고리즘' 카테고리의 다른 글
[Java] BOJ 2212 센서 (0) | 2021.04.28 |
---|---|
[Java] BOJ 2470 두 용액 (0) | 2021.04.26 |
[Java] BOJ 19236 청소년상어 (0) | 2021.04.24 |
[Java] BOJ 20055 컨베이어 벨트 위의 로봇 (0) | 2021.04.24 |
[Java] BOJ 20056 마법사 상어와 파이어볼 (0) | 2021.04.23 |