[백준] 확장 게임

[hye-on]

🔗 확장 게임

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.io.*; import java.util.*; /** * 16:00 START! */ public class Main { /** * 시뮬레이션 문제? * 각 플레이어의 차례마다 확장할 수 있으면 확장 O(nm) * 더 이상 확장할 수 없다면 멈추기 */ static int N, M, P; static int[][] board; static boolean[][] visit; // 항상 모든 칸을 확인하지 않기 위해 public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); P = Integer.parseInt(st.nextToken()); int[] size = new int[P]; st = new StringTokenizer(bf.readLine()); for(int i = 0; i < P; ++i) size[i] = Integer.parseInt(st.nextToken()); int[] score = new int[P]; board = new int[N][M]; visit = new boolean[N][M]; for(int i = 0; i < N; ++i) { String line = bf.readLine(); int j = 0; for(char ch : line.toCharArray()) { if(ch == '.') { board[i][j] = -1; } else if(ch == '#') { visit[i][j] = true; // 방문처리를 해서 탐색하지 못하도록 설정 } else if(ch != '.') { int player = ch - '0'; board[i][j] = player - 1; // player번호를 1번부터가 아닌 0번 부터로 변경 score[player - 1]++; } j++; } } int turn = 0; // 0번 플레이어부터 시작 boolean[] stop = new boolean[P]; // 더이상 움직일 수 없는 플레이어 check int stopCount = 0; while(stopCount < P) { if(!stop[turn]) { int count = extend(turn, size[turn]); // 확장된 크기를 반환 score[turn] += count; if(count == 0) { stop[turn] = true; stopCount++; } } turn = (turn + 1) % P; } for(int s : score) System.out.print(s + " "); } static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; public static int extend(int player, int size) { int count = 0; // dfs Queue q = new LinkedList<>(); for(int i = 0; i < N; ++i) { for(int j = 0; j < M; ++j) { if(board[i][j] == player && !visit[i][j]) { visit[i][j] = true; q.offer(new int[]{i, j, 0}); } } } boolean[][] check = new boolean[N][M]; while(!q.isEmpty()) { int[] node = q.poll(); int x = node[0]; int y = node[1]; int level = node[2]; for(int d = 0; d < 4; ++d) { int nx = x + dx[d]; int ny = y + dy[d]; if(nx >= 0 && nx < N && ny >= 0 && ny < M && board[nx][ny] == -1 && !visit[nx][ny] && !check[nx][ny]) { check[nx][ny] = true; board[nx][ny] = board[x][y]; count++; if(level + 1 == size) continue; // 더 이상 확장 불가능하므로 큐에 넣기 않음! q.offer(new int[]{nx, ny, level + 1}); } } } return count; } } ```

코멘트

- 구현 + bfs 문제였습니다!

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include using namespace std; int n, m, p; vectors; queue, int>>pos[10]; //위치, 거리 char map[1000][1000]; vector castle; // 각 플레이어의 성 개수 int dy[] = { 0,1,0,-1 }; int dx[] = { 1,0,-1,0 }; void bfs(int node) { queue, int>> next_pos; while (!pos[node].empty()) { int curY = pos[node].front().first.first; int curX = pos[node].front().first.second; int d = pos[node].front().second; pos[node].pop(); for (int i = 0; i < 4; i++) { int ny = curY + dy[i]; int nx = curX + dx[i]; if (ny >= n || ny < 0 || nx >= m || nx < 0) continue; if (map[ny][nx] != '.') continue; map[ny][nx] = node + '0'; castle[node]++; if (d + 1 == s[node]) { next_pos.push({ {ny, nx}, 0 }); } else { pos[node].push({ {ny, nx}, d + 1 }); } } } //다음 확장을 시작할 위치 pos[node] = next_pos; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> p; s.resize(p + 1); castle.resize(p + 1, 0); for (int i = 1; i <= p; i++) cin >> s[i]; string str = ""; for (int i = 0; i < n; i++) { cin >> str; for (int j = 0; j < m; j++) { map[i][j] = str[j]; if (map[i][j] - '0' > 0 && map[i][j] - '0' < 10) { int player = map[i][j] - '0'; pos[player].push({ {i,j}, 0 }); castle[player]++; } } } bool changed; do { changed = false; vector prev_castle = castle; for (int i = 1; i <= p; i++) { if (!pos[i].empty()) { bfs(i); } } // 이전 턴과 비교하여 변화가 있는지 확인 for (int i = 1; i <= p; i++) { if (prev_castle[i] != castle[i]) { changed = true; break; } } } while (changed); for (int i = 1; i <= p; i++) cout << castle[i] << " "; return 0; } ```

코멘트

- 시간초과를 안나게 하는 아이디어를 떠올리기 어려웠던것같습니다.