백준 21610. 마법사 상어와 비바라기(상어 시리즈)
04 May 2021문제 바로가기
문제 요약
상어 시리즈 중 최근에 나온 문제, 비바라기 문제이다. 문제를 읽다보면 비바라기 마법을 배워서 사용한다는데 나도 마법좀 배우고싶다. 마법을 시전하면 N*N인 격자의 맵에서 처음 비구름이 생기며 그 위치는 (N, 1), (N, 2), (N-1, 1), (N-1, 2)이다. 이후, 모든 구름은 d 방향으로 s칸 이동하여 비를 내리고 비를 내린 위치에 대해 물복사버그 마법을 시전한다. 물복사버그 마법은 비가 내린 위치의 대각선 칸을 확인하여 물이 있는 만큼 추가로 복사된다.
물복사 마법이 끝나면 전체 맵 중에서 물의 양이 2 이상인 모든 칸에 구름이 생기고 물의 양이 2 줄어들지만, 이번에 비가 내린 칸은 구름이 생기지 않는다. 이때, M 번의 모든 이동이 끝나고 남아있는 물의 양을 구해보아라. 라는 문제이다.
문제 풀이 포인트
굉장히 삼성 코테에서 나올법한 문제 스타일이다. 문제에서 시키는 대로 구현을 하면 되는 문제로 신경써야하는 부분은 비구름이 이동할 때 맵의 바깥으로 나가면 반대편으로 들어온다는 사실만 신경써서 구현하면 되는 문제이다.
어렵지 않은 구현 문제이다.
문제 코드[JAVA]
코드 펼치기
import java.util.*;
public class Main {
static int N, M, map[][];
static ArrayList<int[]> goorm = new ArrayList<>();
static int[] dx = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
static int[] dy = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
map[i][j] = sc.nextInt();
}
}
for (int i = 0; i < 2; i++) {
for (int j = 1; j <= 2; j++) {
goorm.add(new int[] { N - i, j });
}
} // 처음 구름 생성
for (int i = 0; i < M; i++) {
int d = sc.nextInt(); // 방향
int m = sc.nextInt(); // 이동거리
move(d, m); // 구름 이동
rain(); // 비가 내림
copybug(); // 물복사 버그
makegoorm(); // 구름만들기
}
System.out.println(cal());
sc.close();
}
private static int cal() { // 전체 물의 양 계산
int cnt = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cnt += map[i][j];
}
}
return cnt;
}
private static void makegoorm() {
boolean[][] v = new boolean[N + 1][N + 1];
for (int[] p : goorm) { // 기준 구름의 위치에서는 생성하지 않기 위한 방문배열
v[p[0]][p[1]] = true;
}
goorm.clear(); // 구름 리스트 초기화
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (map[i][j] > 1 && !v[i][j]) {
goorm.add(new int[] { i, j }); // 새로 생기는 구름을 리스트에 추가
map[i][j] -= 2;
}
}
}
}
private static void copybug() {
for (int[] p : goorm) {
int cnt = 0;
for (int d = 2; d < 9; d += 2) { // 대각선만 확인하기 위해
int nx = p[0] + dx[d];
int ny = p[1] + dy[d];
if (nx < 1 || nx > N || ny < 1 || ny > N)
continue;
if (map[nx][ny] > 0)
cnt++;
}
map[p[0]][p[1]] += cnt;
}
}
private static void rain() {
for (int[] p : goorm) {
map[p[0]][p[1]]++;
}
}
private static void move(int d, int m) {
int nx = dx[d] * m;
int ny = dy[d] * m;
for (int i = 0; i < goorm.size(); i++) {
int x = goorm.get(i)[0] + nx;
int y = goorm.get(i)[1] + ny;
while(true) { // 칸을 많이 이동해도 계속 체크해줘야하기 때문에 무한반복
if(x >= 1 && x <= N && y >= 1 && y <=N)
break;
if (x < 1)
x += N;
else if (x > N)
x -= N;
if (y < 1)
y += N;
else if (y > N)
y -= N;
}
goorm.get(i)[0] = x;
goorm.get(i)[1] = y;
}
}
}