문제

https://softeer.ai/practice/6265

---

입력

첫 번째 줄에 두 정수 H와 W가 공백 하나를 사이로 두고 주어진다.
다음 H개의 줄에는 각 픽셀의 색상이 주어진다.
이 중 i (1 ≤ i ≤ H)번째 줄의 j (1 ≤ j ≤ W)번째 정수는 Ci, j이다.
그 다음 줄에는 Q가 주어진다.
다음 Q개의 줄에는 연산들이 순서대로 주어진다.
각 줄에는 세 개의 정수 i, j, c가 공백 하나를 사이로 두고 주어진다.

---

출력

모든 연산을 완료한 후, 최종 이미지를 H개의 줄에 W개의 정수를 공백 하나씩을 사이로 두고 출력한다.

---

풀이

제한조건

• 1 ≤ H, W ≤ 128
  모든 i, j (1 ≤ i ≤ H, 1 ≤ j ≤ W) 에 대해:
  1 ≤ Ci, j ≤ 109
  1 ≤ Q ≤ 500

각 연산 (i, j, c)에 대해:
1 ≤ i ≤ H
1 ≤ j ≤ W
1 ≤ c ≤ 109
주어지는 모든 수는 정수이다.

접근방법

크게 본다면 탐색문제이다.

다만, 특정 구역의 색상이 최대 500번 변경되며, 주변 색상과 동일한 색으로 변경될 경우 주변 영역도 같이 변경된다.

즉, 탐색이 필요하지만, 색상 변경이 미치는 구역이 점점 커진다.
따라서 수정을 염두해둔 탐색이 필요하다.

전체 크기 128 X 128의 탐색. 500번의 색상 변경.
(항상 완전탐색을 하더라도, 시간안에는 풀 수 있을듯 하다.
약 5000만번 연산)

평소와 조금 다른 방식으로 풀고 싶었다.
일단 처음 탐색을 하면서, 같은 색상으로 이루어진 그룹을 생성한다.

입력 : 1 1 2 2 2 1 1 2 2
->
그룹 : 1 1 2 2 2 3 3 4 4

그 다음, 각 그룹이 어떤 그룹과 인접한지 기록해둔다.
예를 들자면 2번 그룹은 1,3 그룹과 인접해있다.

이제 색상 변경에 대해서 처리해보자.
만약 완전 탐색 형식으로 구성하였다면, 특정 지점부터 4방향으로 탐색하며 모두 색상을 변경하면 된다.
하지만, 앞서 탐색을 통해 색상의 그룹과 인접 그룹, 색을 모두 구했기 때문에, 전체 맵을 탐색할 필요가 없다.

입력 : 1 1 2 2 2 1 1 2 2
->
그룹 : 1 1 2 2 2 3 3 4 4

2번 그룹의 색상을 1로 변경.
code : map.put(group, color);

인접한 그룹이 어떤것인지, 인접 그룹의 색상이 무엇인지도 알기 때문에
현재 그룹과 같은색이라면, 해당 그룹의 색도 변경하면 끝이다.

맵의 크기가 더 크거나, 변경 수(Q)가 더 크다면, 훨씬 효율적인 방식이 될 수 있다.
(특정 좌표에서부터 연결된 모든 좌표를 한칸 한칸 확인할 필요가 없기 때문)

정리하자면 아래의 흐름이다

1. 같은 색상을 그룹으로 묶는다.
2. 각 그룹의 색, 인접 그룹의 ID를 찾는다.
3. 변경 연산을 수행한다.
	a. 특정 좌표가 속한 그룹의 색상 변경
    b. 인접한 그룹의 색상 변경
4. 각 좌표의 그룹 ID를 기준으로 색상을 찾아 출력

테스트 케이스에서 최악의 경우 약 0.6초, 평균 0.1초에서 모두 해결할 수 있다.
문제의 제한 2초는 매우 넉넉한 편

---

코드

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static int H, W, Q;
    static StringBuilder sb;

    static Map<Integer, Integer> map = new HashMap();
    static int[][] arr, visit;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        String[] inputs = in.readLine().split(" ");
        H = stoi(inputs[0]);
        W = stoi(inputs[1]);
        visit = new int[H][W];
        arr = new int[H][W];
        for(int i = 0; i < H; ++i){
            inputs = in.readLine().split(" ");
            for(int j = 0; j < W; ++j){
                arr[i][j] = stoi(inputs[j]);
            }
        }

        // 탐색
        int groupId = 1;
        for(int i = 0; i < H; ++i){
            for(int j = 0; j < W; ++j){
                if(visit[i][j] == 0){
                    search(i,j, groupId);
                    // Key : groupID, Value : 해당 그룹의 색
                    map.put(groupId, arr[i][j]);
                    groupId++;
                }
            }
        }

        // 그룹별로 인접 그룹을 다시 구하자.
        Set<Integer>[] adj = new HashSet[groupId + 1];
        for(int i = 0 ; i < groupId + 1; ++i)
            adj[i] = new HashSet();

        for(int i = 0; i < H; ++i){
            for(int j = 0; j < W; ++j){
                for(int d = 0; d < 4; ++d){
                    int nextX = i + dx[d];
                    int nextY = j + dy[d];
                    // 범위 내부
                        if(0 <= nextX && nextX < H && 0 <= nextY && nextY < W && arr[i][j] != arr[nextX][nextY]){
                            adj[visit[i][j]].add(visit[nextX][nextY]);
                        }
                }
            }
        }
        
    
        
        Q = stoi(in.readLine());
        for(int i = 0; i < Q; ++i){
            inputs = in.readLine().split(" ");
            int x = stoi(inputs[0]) - 1;
            int y = stoi(inputs[1]) - 1;
            int color = stoi(inputs[2]);

            int group = visit[x][y];
            int org = map.get(group);
            map.put(group, color);
            Queue<Integer> q = new ArrayDeque();
            boolean[] check = new boolean[groupId+1];
            check[group] = true;
            for(int adjId : adj[group]){
                if(map.get(adjId) == org)
                    q.add(adjId);
            }
            while(!q.isEmpty()){
                int id = q.poll();
                if(map.get(id) == org){
                    map.put(id, color);
                    for(int adjId : adj[id]){
                        if(map.get(adjId) == org && !check[adjId]){
                            q.add(adjId);
                            check[adjId] = true;
                        }
                    }
                }
            }
        }

        // print
        for(int i = 0; i < H; ++i){
            for(int j = 0; j < W; ++j){
                sb.append(map.get(visit[i][j]));
                if(j != W-1)
                    sb.append(" ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb);
    }

    public static void search(int x, int y, int groupId){
        Queue<int[]> q = new ArrayDeque();
        q.add(new int[] {x,y});
        visit[x][y] = groupId;

        while(!q.isEmpty()){
            int[] pos = q.poll();

            for(int d = 0; d < 4; ++d){
                int nextX = pos[0] + dx[d];
                int nextY = pos[1] + dy[d];
                // 범위 내부
                if(0 <= nextX && nextX < H && 0 <= nextY && nextY < W){
                    if(visit[nextX][nextY] == 0 && arr[x][y] == arr[nextX][nextY]){
                        visit[nextX][nextY] = groupId;
                        q.add(new int[]{nextX, nextY});
                    }
                }
            }
        }
    }
    public static int stoi(String s){
        return Integer.parseInt(s);
    }
}