[Gold II] 벽 부수고 이동하기 4 - 16946
성능 요약
메모리: 84284 KB, 시간: 656 ms
분류
너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)
문제 설명
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.
각각의 벽에 대해서 다음을 구해보려고 한다.
- 벽을 부수고 이동할 수 있는 곳으로 변경한다.
- 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.
출력
맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.
풀이
처음에는 벽이 있는 곳에서 모두 bfs를 돌렸는데 시간초과가 났다
두 번째 테스트 케이스
4 5
11001
00111
01010
10101
와 같은 경우에 0이 이어져있는 부분을 중복해서 방문하기 때문에 연산이 낭비되고 있기 때문이다.
그래서 0인 경우에 이동할 수 있는 블럭의 개수를 한 번의 bfs로 세었다.
그리고 result 배열에 각 개수를 저장하였다.
이 cnt를 같은 분리집합(이동 가능한 경우)에 있는 값에 모두 저장하기 위해 bfs를 수행하고, 지나온 경로들을 다시 큐에 저장해서 result 값을 업데이트하였다.
static void bfs(int r, int c, int cnt) {
Queue<int[]> q = new LinkedList<>();
Queue<int[]> pick = new LinkedList<>();
q.add(new int[]{r, c});
while (!q.isEmpty()) {
int[] tmp = q.poll();
int tr = tmp[0];
int tc = tmp[1];
if (visited[tr][tc] !=0) continue;
visited[tr][tc] = cnt;
pick.add(tmp);
result[r][c]++; // 방문 가능한 곳
for (int d = 0; d < 4; d++) {
int nr = tr + dr[d];
int nc = tc + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] != cnt && map[nr][nc] == 0)
q.add(new int[]{nr, nc});
}
}
int ans = result[r][c];
// ans값 저장하기
while (!pick.isEmpty()) {
int[] tmp = pick.poll();
int tr = tmp[0];
int tc = tmp[1];
result[tr][tc] = ans;
}
}
그리고 답을 출력할 때는 map 값이 0인 경우에는 0, 1인 경우에는 사방 탐색을 통해 각 값의 합을 더하였다.
그런데 위에 말한 테스트 케이스 2의 경우 같은 분리집합에 속한 경우의 수는 한 번만 더해줘야 한다.
그래서 bfs를 돌 때 같은 분리 집합에 속한 경우는 visited 배열의 값을 모두 같게 지정해서 사방탐색의 index가 다른 index와 visited값이 같을 경우 해당 값은 더하지 않았다.
static int find(int r, int c) {
if (map[r][c] == 0) return 0;
// 네 방향을 조사하고 만약 특정 두 방향이 서로 연결 가능한 경우에는 중복 빼주기
int ans = 1;
label: for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] == 0) {
for (int j = 0; j < d; j++) {
int checkr = r+dr[j];
int checkc = c+dc[j];
if (checkr >=0 && checkr< N && checkc>=0 && checkc< M && visited[nr][nc] == visited[checkr][checkc])
continue label;
}
ans+=result[nr][nc];
}
}
return ans;
}
전체 코드
package BOJ.Gold.g2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ_16946_벽부수고이동하기4 {
static int N, M;
static int[][] map;
static int[][] result;
static int[] dr = {1, -1, 0, 0};
static int[] dc = {0, 0, 1, -1};
static int[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
result = new int[N][M];
visited = new int[N][M];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++)
map[i][j] = input.charAt(j) - '0';
}
int cnt = 1;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
if (map[i][j] == 0 && visited[i][j]==0)
bfs(i, j, cnt++);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
sb.append(find(i, j)%10); // 10으로 나눈 나머지인거 주의하기
sb.append("\n");
}
System.out.print(sb);
}
static void bfs(int r, int c, int cnt) {
Queue<int[]> q = new LinkedList<>();
Queue<int[]> pick = new LinkedList<>();
q.add(new int[]{r, c});
while (!q.isEmpty()) {
int[] tmp = q.poll();
int tr = tmp[0];
int tc = tmp[1];
if (visited[tr][tc] !=0) continue;
visited[tr][tc] = cnt;
pick.add(tmp);
result[r][c]++; // 방문 가능한 곳
for (int d = 0; d < 4; d++) {
int nr = tr + dr[d];
int nc = tc + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] != cnt && map[nr][nc] == 0)
q.add(new int[]{nr, nc});
}
}
int ans = result[r][c];
// ans값 저장하기
while (!pick.isEmpty()) {
int[] tmp = pick.poll();
int tr = tmp[0];
int tc = tmp[1];
result[tr][tc] = ans;
}
}
static int find(int r, int c) {
if (map[r][c] == 0) return 0;
// 네 방향을 조사하고 만약 특정 두 방향이 서로 연결 가능한 경우에는 중복 빼주기
int ans = 1;
label: for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] == 0) {
for (int j = 0; j < d; j++) {
int checkr = r+dr[j];
int checkc = c+dc[j];
if (checkr >=0 && checkr< N && checkc>=0 && checkc< M && visited[nr][nc] == visited[checkr][checkc])
continue label;
}
ans+=result[nr][nc];
}
}
return ans;
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 1937 - 욕심쟁이 판다 (자바 Java) (0) | 2022.11.08 |
---|---|
[백준] 1202 - 보석 도둑 (자바 Java) (0) | 2022.11.07 |
[백준] 1644 - 소수의 연속합 (자바 Java) (0) | 2022.10.30 |
[백준] 1806 - 부분합 (자바 Java) (0) | 2022.10.30 |
[백준] 1987 - 알파벳 (자바 Java) (0) | 2022.10.28 |