Tags
- Dynamic Programming
- ๋ฌธ์์ด
- stack
- SpringBoot
- ๊ตฌํ
- queue
- ๊น์ด ์ฐ์ ํ์
- Java
- greedy
- Python
- sort
- ์ ์๋ก
- BFS
- DP
- ์๋ฃ๊ตฌ์กฐ
- ๋ฐฑํธ๋ํน
- LV2
- ๊ต์ฌ
- ์ํ
- ๊ทธ๋ํ ํ์
- ๋๋น ์ฐ์ ํ์
- Study
- Brute Force Algorithm
- ์๋ฎฌ๋ ์ด์
- PGM
- ๊ทธ๋ํ ์ด๋ก
- BOJ
- ์ ๋ ฌ
- CodingTest
- dfs
Archives
๊ธฐ๋ก๋ฐฉ
BOJ_17143 : ๋์์ ๋ณธ๋ฌธ
๐ธ ๋ฌธ์ ๋ถ์ ๐ธ
- R x C ๊ฒฉ์ํ์ M๋ง๋ฆฌ์ ์์ด๊ฐ ์๋ค.
- 1์ด์ ๋์์์ด ์ค๋ฅธ์ชฝ์ผ๋ก ํ ์นธ ์ด๋ํ๊ณ , ์์ด๋ค์ ์๋ ๋งํผ ์ด๋ํ๋ค.
- ๋์์์ด ์ด๋ ํ์ ๋ ๊ฐ์ ์ด์ ๊ฐ์ฅ ์์ชฝ์ ์๋ ์์ด๋ฅผ ์ก๋๋ค.
- ์์ด๊ฐ ๊ฒน์น๋ฉด ํฌ๊ธฐ๊ฐ ํฐ ์์ด๊ฐ ๋ค ์ก์๋จน๊ณ ํผ์ ๋จ๋๋ค.
- ์์ด๊ฐ ์ด๋ํ ๋ ๋ฒฝ์ ๋ถ๋ํ๋ฉด ๋ฐ๋ ๋ฐฉํฅ์ผ๋ก ๋ง์ ์ด๋ํ๋ค.
- ๋์์์ด ๋๊น์ง ์ด๋ํ์ ๋ ์ก์ ์์ด ํฌ๊ธฐ์ ํฉ์ ์ถ๋ ฅํ๋ค.
- 1์ด์ ๋์์์ด ์ค๋ฅธ์ชฝ์ผ๋ก ํ ์นธ ์ด๋ํ๊ณ , ์์ด๋ค์ ์๋ ๋งํผ ์ด๋ํ๋ค.
- ๋์์ ์ด๋ ํ ์์ด๋ค์ ์์ง์์ ์์๋๋ก ๊ตฌํํ๋ค.
๐ธ ์ฝ๋ ๐ธ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static class Shark {
int s, d, z;
public Shark(int s, int d, int z) {
this.s = s;
this.d = d;
this.z = z;
}
}
private static int R, C, M, ans;
private static Shark[][] map, temp;
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, 1, -1};
public static void main(String[] args) throws IOException {
// Input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new Shark[R + 1][C + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = new Shark(
Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) - 1,
Integer.parseInt(st.nextToken()));
}
// ๋์์ ์ด๋
for (int i = 1; i <= C; i++) {
// ์์ด ์์ผ๋ฉด ์ก๊ธฐ
for (int j = 1; j <= R; j++) {
if (map[j][i] != null) {
ans += map[j][i].z;
M--;
map[j][i] = null;
break;
}
}
// ์์ด ์ด๋
temp = new Shark[R + 1][C + 1];
for (int j = 1; j <= R; j++) {
for (int k = 1; k <= C; k++) {
if (map[j][k] != null) { // ์์ด ๋ฐ๊ฒฌ
move_shark(j, k, map[j][k]); // ์ด๋
}
}
}
deepCopy();
}
System.out.println(ans);
}
private static void move_shark(int r, int c, Shark shark) {
// ์์ด ์ด๋
int dd = shark.d % 2 == 0 ? 1 : -1;
int dr = r, dc = c;
for (int i = 0; i < shark.s; i++) {
dr = r + dx[shark.d];
dc = c + dy[shark.d];
if (1 > dr || dr > R || 1 > dc || dc > C) {
shark.d += dd;
dd *= -1;
i--;
continue;
}
r = dr;
c = dc;
}
// ์์ด ์์น ์ ์ฅ
if (temp[dr][dc] == null) {
temp[dr][dc] = shark;
} else {
temp[dr][dc] = temp[dr][dc].z > shark.z ? temp[dr][dc] : shark;
}
}
private static void deepCopy() {
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
if (temp[i][j] != null)
map[i][j] = temp[i][j];
else {
map[i][j] = null;
}
}
}
}
private static void print() {
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
if (map[i][j] != null) {
System.out.print('S' + " ");
} else {
System.out.print('O' + " ");
}
}
System.out.println();
}
}
}
๐ธ ์ฝ๋ ํด์ ๐ธ
- ๋์์์ด 1๋ถํฐ C๊น์ง ์ด๋ํ๋ค.
- ๊ฐ์ ์ด์ ์์ด๊ฐ ์๋ค๋ฉด, ๊ฐ์ฅ ์์ ์๋ ์์ด๋ฅผ ์ก๊ณ ์นด์ดํธ ํ๋ค.
- ์์ด๊ฐ ์ด๋ํ๋ค.
- map์์ ์์ด๋ฅผ ๋ฐ๊ฒฌํ๋ฉด move_shark ๋ฉ์๋์์ ์ด๋ ํ temp์ ์ ์ฅํ๋ค.
- ์์ด์ ์๋ ๋งํผ ์ด๋ํ๋๋ฐ ๋ฒฝ์ ๋ถ๋ํ๋ฉด ๋ฐ๋ ๋ฐฉํฅ์ผ๋ก ๋ง์ ์ด๋ํ๋ค.
- ์ง์ ๋ฐฉํฅ์ด๋ผ๋ฉด +1, ํ์ ๋ฐฉํฅ์ด๋ผ๋ฉด -1์ ํ๋ฉด ๋ฐ๋ ๋ฐฉํฅ์ด ๋๋ค.
- ์์ด์ ์์น๋ฅผ temp์ ์ ์ฅ ํ ๋ ํฌ๊ธฐ๊ฐ ํฐ ์์ด๋ง ๋จ๊ธด๋ค.
- temp๋ฅผ map์ผ๋ก ๋ณต์ฌํด map ์ ๋ณด๋ฅผ ์ ๋ฐ์ดํธํ๋ค.
- map์์ ์์ด๋ฅผ ๋ฐ๊ฒฌํ๋ฉด move_shark ๋ฉ์๋์์ ์ด๋ ํ temp์ ์ ์ฅํ๋ค.
- ๋์์์ด ์ด๋ํ๋ฉฐ ์ก์ ์์ด์ ํฌ๊ธฐ์ ํฉ์ ์ถ๋ ฅํ๋ค.
๐ธ end ๐ธ
- ๋ฐ๋๋ฐฉํฅ์ if๋ฌธ์ผ๋ก ํ๋จํ๊ธฐ๋ณด๋ค, %์ฐ์ฐ์ ์ด์ฉํ๋๊ฒ ์ค๋ฒํค๋๊ฐ ๋ ๋ฎ์์ ๊ฒ ๊ฐ๋ค.
728x90
'CodingTest > Java' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Lv.1 : ์ผ์ด์ฌ (0) | 2023.04.10 |
---|---|
Lv.1 : ์ซ์ ์ง๊ฟ (0) | 2023.04.10 |
BOJ_16928 : ๋ฑ๊ณผ ์ฌ๋ค๋ฆฌ ๊ฒ์ (0) | 2023.04.07 |
BOJ_17070 : ํ์ดํ ์ฎ๊ธฐ๊ธฐ 1 (0) | 2023.04.07 |
BOJ_14889 : ์คํํธ์ ๋งํฌ (0) | 2023.04.07 |