(16920) 확장 게임 (Java)
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 5581 | 1288 | 859 | 22.179% |
문제
구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다.
게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.
각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다. 플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다. 성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.
모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.
입력
첫째 줄에 격자판의 크기 N, M과 플레이어의 수 P가 주어진다. 둘째 줄에는 S1, S2, ...SP가 주어진다.
다음 N개의 줄에는 게임판의 상태가 주어진다. '.'는 빈 칸, '#'는 벽, '1', '2', ..., '9'는 각 플레이어의 성이다.
모든 플레이어는 적어도 하나의 성을 가지고 있으며, 게임에 참가하지 않는 플레이어의 성이 있는 경우는 없다.
출력
플레이어 1이 가진 성의 수, 2가 가진 성의 수, ..., P가 가진 성의 수를 공백으로 구분해 출력한다.
제한
1 ≤ N, M ≤ 1,000
1 ≤ P ≤ 9
1 ≤ Si ≤ 109
예제 입력 1
3 3 2
1 1
1..
...
..2
예제 출력 1
6 3
예제 입력 2
3 3 2
1 1
1.1
...
..2
예제 출력 2
7 2
예제 입력 3
4 4 2
1 1
1...
....
....
...2
예제 출력 3
10 6
예제 입력 4
4 4 2
1 1
1..1
....
....
...2
예제 출력 4
11 5
예제 입력 5
4 4 2
2 1
1..1
....
....
...2
예제 출력 5
14 2
예제 입력 6
4 4 2
3 1
1..1
....
....
...2
예제 출력 6
14 2
예제 입력 7
4 4 2
1 1
1..1
#.##
....
...2
예제 출력 7
7 6
예제 입력 8
4 4 2
2 1
1..1
#.##
....
...2
예제 출력 8
10 3
예제 입력 9
3 4 4
1 1 1 1
....
#...
1234
예제 출력 9
1 4 3 3
출처
문제를 번역한 사람: baekjoon
데이터를 추가한 사람: hoxymola
알고리즘 분류
그래프 이론
그래프 탐색
너비 우선 탐색
Solution
1 시간초과
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int n, m, p; // 맵 사이즈, 플레이어 수
public static char[][] map; // 게임 맵 (격자판)
public static boolean[][] visited; // 방문처리
public static int[] s; // 플레이어별 최대 확장 거리
public static int[] cnt; // 플레이어별 성 개수
public static int[] dx = {-1, 1, 0, 0}; // 인접칸 탐색을 위한 변화값
public static int[] dy = {0, 0, -1, 1}; // 인접칸 탐색을 위한 변화값
public static class Node {
int x, y;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static Queue<Node>[] qs; // 플레이어 수만큼 큐를 가져가기 위함
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 맵의 열 크기
m = Integer.parseInt(st.nextToken()); // 맵의 행 크기
p = Integer.parseInt(st.nextToken()); // 플레이어 수
map = new char[n][m]; // 맵 세팅
visited = new boolean[n][m]; // 방문처리
qs = new Queue[p+1]; // 플레이어 1부터 index 1에 넣기 위해 사이즈 1 크게 잡음
for(int i = 0; i <= p; i++) {
qs[i] = new LinkedList<Node>(); // 배열의 각 원소에 큐 세팅
}
s = new int[p+1]; // 플레이어 1부터 index 1에 넣기 위해 사이즈 1 크게 잡음
cnt = new int[p+1]; // 플레이어 1부터 index 1에 넣기 위해 사이즈 1 크게 잡음
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= p; i++) {
s[i] = Integer.parseInt(st.nextToken()); // 플레이어별 최대 확장 거리 세팅
}
for(int i = 0; i < n; i++) {
String[] strArr = br.readLine().split("");
for(int j = 0; j < m; j++) {
char ch = strArr[j].charAt(0);
map[i][j] = ch; // 플레이어 성, 벽 세팅
// 성이 있는 칸이면 각 플레이어별 시작 노드로 세팅
if(ch != '.' && ch != '#') {
int player = Character.getNumericValue(ch);
qs[player].offer(new Node(i, j));
visited[i][j] = true;
cnt[player]++;
}
}
}
// 아무 플레이어도 더이상 성을 확장할 수 없을때까지 라운드 진행
while(true) {
if(round()) break;
}
// 정답 출력
for(int i = 1; i <= p; i++) {
bw.write(String.valueOf(cnt[i]) + " ");
}
bw.flush();
bw.close();
br.close();
}
public static boolean round() {
int emptyPlayer = 0; // 플레이어의 큐가 비어있는지 체크를 위함
// 플레이어별로 돌아가며 라운드 진행
for(int player = 1; player <= p; player++) {
// 해당 플레이어의 큐가 비어있다면 더이상 성을 확장할 수 없다는 것이므로 emptyPlayer++ 하고 다음 플에이어 턴으로 넘김
if(qs[player].isEmpty()) {
emptyPlayer++;
continue;
}
// 한 명의 플레이어씩 턴을 진행
turnStart(player);
}
return emptyPlayer == p; // 모든 플레이어의 큐가 비어있으면 true를 리턴하여 위에서 while문 break하도록 함
}
public static void turnStart(int player) {
// 플레이어의 최대 확장 거리 만큼 성 확장 진행 (중요)
for(int ext = 0; ext < s[player]; ext++) {
// 처음에 들고 있는 큐의 사이즈 만큼만 확장을 진행해야 한 턴이 끝나는 것이기에 size 만큼만 탐색
// 변수를 별도로 잡지 않고 qs[player].size()를 사용하게 되면 탐색 과정에서 추가로 큐에 원소가 들어오게 되면,
// 진작 턴이 종료되어야 했음에도 더 턴을 이어나가는 꼴이 됨
int size = qs[player].size();
for(int i = 0; i < size; i++) {
Node cur = qs[player].poll();
for(int k = 0; k < 4; k++) {
int nx = cur.x + dx[k];
int ny = cur.y + dy[k];
if(isNotRange(nx, ny) || visited[nx][ny] || map[nx][ny] == '#') continue;
qs[player].offer(new Node(nx, ny));
visited[nx][ny] = true;
map[nx][ny] = Character.forDigit(player, 10);
cnt[player]++;
}
}
}
}
public static boolean isNotRange(int x, int y) {
return (x < 0 || x >= n || y < 0 || y >= m) ? true : false;
}
}2
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int n, m, p; // 맵 사이즈, 플레이어 수
public static char[][] map; // 게임 맵 (격자판)
public static boolean[][] visited; // 방문처리
public static int[] s; // 플레이어별 최대 확장 거리
public static int[] cnt; // 플레이어별 성 개수
public static int[] dx = {-1, 1, 0, 0}; // 인접칸 탐색을 위한 변화값
public static int[] dy = {0, 0, -1, 1}; // 인접칸 탐색을 위한 변화값
public static class Node {
int x, y, dis;
Node(int x, int y, int dis) {
this.x = x;
this.y = y;
this.dis = dis;
}
}
public static Queue<Node>[] qs; // 플레이어 수만큼 큐를 가져가기 위함
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 맵의 열 크기
m = Integer.parseInt(st.nextToken()); // 맵의 행 크기
p = Integer.parseInt(st.nextToken()); // 플레이어 수
map = new char[n][m]; // 맵 세팅
visited = new boolean[n][m]; // 방문처리
qs = new Queue[p+1]; // 플레이어 1부터 index 1에 넣기 위해 사이즈 1 크게 잡음
for(int i = 0; i <= p; i++) {
qs[i] = new LinkedList<Node>(); // 배열의 각 원소에 큐 세팅
}
s = new int[p+1]; // 플레이어 1부터 index 1에 넣기 위해 사이즈 1 크게 잡음
cnt = new int[p+1]; // 플레이어 1부터 index 1에 넣기 위해 사이즈 1 크게 잡음
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= p; i++) {
s[i] = Integer.parseInt(st.nextToken()); // 플레이어별 최대 확장 거리 세팅
}
for(int i = 0; i < n; i++) {
String[] strArr = br.readLine().split("");
for(int j = 0; j < m; j++) {
char ch = strArr[j].charAt(0);
map[i][j] = ch; // 플레이어 성, 벽 세팅
// 성이 있는 칸이면 각 플레이어별 시작 노드로 세팅
if(ch != '.' && ch != '#') {
int player = Character.getNumericValue(ch);
qs[player].offer(new Node(i, j, 0));
visited[i][j] = true;
cnt[player]++;
}
}
}
// 아무 플레이어도 더이상 성을 확장할 수 없을때까지 라운드 진행
while(true) {
if(round()) break;
}
// 정답 출력
for(int i = 1; i <= p; i++) {
bw.write(String.valueOf(cnt[i]) + " ");
}
bw.flush();
bw.close();
br.close();
}
public static boolean round() {
int emptyPlayer = 0; // 플레이어의 큐가 비어있는지 체크를 위함
// 플레이어별로 돌아가며 라운드 진행
for(int player = 1; player <= p; player++) {
// 해당 플레이어의 큐가 비어있다면 더이상 성을 확장할 수 없다는 것이므로 emptyPlayer++ 하고 다음 플에이어 턴으로 넘김
if(qs[player].isEmpty()) {
emptyPlayer++;
continue;
}
// 한 명의 플레이어씩 턴을 진행
turnStart(player);
}
return emptyPlayer == p; // 모든 플레이어의 큐가 비어있으면 true를 리턴하여 위에서 while문 break하도록 함
}
public static void turnStart(int player) {
while(!qs[player].isEmpty()) {
// 확장 횟수 모두 소진 시 다음턴에 이어서 탐색 진행
if(qs[player].peek().dis == s[player]) {
// 이때 거리는 다시 0으로 초기화(턴이 바뀌므로)
resetDis(qs[player], player);
return;
}
Node cur = qs[player].poll();
// 탐색 중 더이상 확장할 수 없는 경우 return
if(cur == null) return;
for(int k = 0; k < 4; k++) {
int nx = cur.x + dx[k];
int ny = cur.y + dy[k];
if(isNotRange(nx, ny) || visited[nx][ny] || map[nx][ny] == '#') continue;
qs[player].offer(new Node(nx, ny, cur.dis+1));
visited[nx][ny] = true;
map[nx][ny] = Character.forDigit(player, 10);
cnt[player]++;
}
}
}
public static void resetDis(Queue<Node> q, int player) {
for(int i = 0; i < q.size(); i++) {
if(q.peek().dis == s[player]) {
Node tmp = q.poll();
tmp.dis = 0;
q.offer(tmp);
}
}
}
public static boolean isNotRange(int x, int y) {
return (x < 0 || x >= n || y < 0 || y >= m) ? true : false;
}
}Feedback
처음에 문제의 의도를 잘못 파악하였다.. 지문이 애매하게 나와있어서 한참 생각해서 겨우 문제의 본래 의도를 파악했다..
테스트케이스 5에서 내가 이해한 바로는 플레이어 1 : 플레이어 2 = 13: 3 이 나와야 하는 정답 출력이 14 : 2라고 되어있어서 한참 생각했다..결국 s에 따라, 예를 들어 s가 2 라면 처음에 성이 있는 각 칸에서 상, 하, 좌, 우로 1칸씩 이동하고 또 거기에서 추가로 1칸씩 이동하는 개념이다.
시간초과의 원인은 3중첩 반복문이었다. 플레이어마다 확장할 수 있는 거리가 다르다보니, 탐색 과정에서 어디까지 탐색되었을때 멈추고, 다음 턴에 이어서 탐색하도록 해야할지 이 방법을 생각해내는 것이 매우 어려웠다.
해결 방법은 Node 클래스에 확장 횟수(거리)를 의미하는 dis 변수를 추가하였다. 탐색 시 큐에 인접 칸을 offer할때 거리를 +1해서 담아주었다. 그리고 for문을 제거하고 가장 앞에 있는 큐의 원소가 해당 플레이어의 최대 확장 거리와 같다면, 그 원소부터는 다음턴에 탐색할 수 있도록 dis 변수만 0으로 초기화 하고 턴을 return 하였다.
이번 문제는 특히 어려웠다... 좀 더 많은 문제를 접하고, 다른 사람들의 풀이를 보면서 사고력을 키워야할 필요가 있다.
