https://www.acmicpc.net/problem/16946
난이도
골드2
문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.
각각의 벽에 대해서 다음을 구해보려고 한다.
벽을 부수고 이동할 수 있는 곳으로 변경한다.
그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.
출력
맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.
내 코드
744ms
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[][] map, groupId, result;
static int[] groupSize;
static boolean[][] visited;
static int groupCount = 0;
static final int[] dx = {0, 0, 1, -1};
static final int[] dy = {1, -1, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
groupId = new int[N][M];
result = new int[N][M];
visited = new boolean[N][M];
List<Integer> groupSizes = new ArrayList<>();
groupSizes.add(0);
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = line.charAt(j) - '0';
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0 && !visited[i][j]) {
groupSizes.add(bfs(i, j, groupCount + 1));
groupCount++;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 1) {
result[i][j] = getGroupSum(i, j, groupSizes);
}
sb.append(result[i][j]);
}
sb.append("\n");
}
System.out.print(sb.toString());
}
static int bfs(int x, int y, int id) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, y});
visited[x][y] = true;
groupId[x][y] = id;
int size = 1;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int d = 0; d < 4; d++) {
int nx = cur[0] + dx[d];
int ny = cur[1] + dy[d];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (!visited[nx][ny] && map[nx][ny] == 0) {
visited[nx][ny] = true;
groupId[nx][ny] = id;
queue.add(new int[]{nx, ny});
size++;
}
}
}
}
return size;
}
static int getGroupSum(int x, int y, List<Integer> groupSizes) {
Set<Integer> uniqueGroups = new HashSet<>();
int sum = 1;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
if (map[nx][ny] == 0) {
int gid = groupId[nx][ny];
if (!uniqueGroups.contains(gid)) {
uniqueGroups.add(gid);
sum += groupSizes.get(gid);
}
}
}
}
return sum % 10;
}
}4332ms
import java.util.*;
import java.io.*;
class Main {
static int N, M;
static int[][] map, groupMap, ansMap;
static ArrayList<Integer> zeroGroupCount;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws Exception{
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];
groupMap = new int[N][M];
ansMap = new int[N][M];
for(int i = 0; i < N; i++){
String str = br.readLine();
for(int j = 0; j < M; j++){
map[i][j] = str.charAt(j) - '0';
}
}
zeroGroupCount = new ArrayList<>();
bfs();
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(map[i][j] == 1){
int cnt = 1;
HashSet<Integer> set = new HashSet<>();
for(int k = 0; k < 4; k++){
int nx = i + dx[k];
int ny = j + dy[k];
if(!inRange(nx, ny)){
continue;
}if(set.contains(groupMap[nx][ny])){
continue;
}if(map[nx][ny] == 1){
continue;
}
set.add(groupMap[nx][ny]);
cnt += zeroGroupCount.get(groupMap[nx][ny] - 1);
}
ansMap[i][j] = cnt % 10;
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
System.out.print(ansMap[i][j]);
}
System.out.println();
}
}
public static void bfs(){
Queue<int[]> q = new LinkedList<>();
boolean[][] visited = new boolean[N][M];
int idx = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(map[i][j] == 0 && !visited[i][j]){
q.clear();
q.add(new int[]{i, j});
visited[i][j] = true;
groupMap[i][j] = ++idx;
int tmpCnt = 1;
while(!q.isEmpty()){
int[] now = q.poll();
for(int k = 0; k < 4; k++){
int nx = now[0] + dx[k];
int ny = now[1] + dy[k];
if(!inRange(nx, ny)){
continue;
}if(visited[nx][ny] || map[nx][ny] == 1){
continue;
}
groupMap[nx][ny] = idx;
visited[nx][ny] = true;
q.add(new int[]{nx, ny});
tmpCnt++;
}
}
zeroGroupCount.add(tmpCnt);
}
}
}
}
public static boolean inRange(int x, int y){
return 0 <= x && x < N && 0 <= y && y < M;
}
}우선 0인 부분만 먼저 각 위치별로 0으로 이어진 갯수가 몇개인지 세는 BFS를 돌려놓고, 2차원 배열에서 왼쪽 상단부터 오른쪽 하단까지 1인 위치에서 상하좌우에 0인 곳들의 수를 숫자만 더하면 바로 현 위치에서 벽을 부쉈을 때 이어진 갯수를 파악할 수 있게 구현하였다.
신기한건, 매우 유사한 로직인데 속도가 거의 6배정도 차이난다는 것이다..
다른 사람들의 코드를 참고해도 로직이 매우 비슷했는데 왜이렇게 차이가 날까 고민했는데
단순히 출력을 할 때 StringBuilder 사용을 하고 안하고의 차이였다.
대량의 출력이 필요한 경우 StringBuilder를 사용하는게 좋다고 알고는 있었지만,
이렇게 많이 차이가 나는지 몰랐다. 앞으로 StringBuilder를 사용해야겠다.
