https://www.acmicpc.net/problem/16234

1. 아이디어

• 구현, 시뮬레이션
• BFS: 국경선 오픈 및 같은 연합인 칸들 찾기

• 인구 이동이 없을 때까지 반복

  • breakFlag == true인 경우, 반복 종료

• 2중 for문으로 각 나라 칸들 차례로 확인

  
  

1) 오픈 가능한 국경선을 따라가며 연합을 탐색

• BFS 수행

  • 연합의 총 인구 수, 연합을 이루는 나라 칸 수 저장

  • 연합을 이루는 칸을 리스트에 저장

• l <= |map[y][x] - map[ny][nx]| <= r 인 경우, 탐색 확장

  
  

2) 저장한 연합 칸 리스트를 통해 인구 이동 수행

• 리스트에 저장된 연합 칸 개수 > 1인 경우

  • 인구 이동 수행

  • breakFlag = false; 처리

2. 자료구조

• int[][] map: 각 나라 칸의 인구 수

• boolean[][] visited

• Queue<Node>, LinkedList<Node>: BFS 수행

  • Node: 현재 탐색 지점 (y, x)

• List<Node>, ArrayList<Node>: BFS 탐색한 연합 칸들 저장

코드

import java.io.*;
import java.util.*;

class Node {
    public int y, x;

    public Node(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static int n;                        // n x n 맵
    static int l, r;                    // 국경선을 공유하는 두 나라의 인구 차이가 l명 이상, r명 이하
    static int[][] map;
    static int numOfDay;                // 출력, 인구 이동이 발생하는 일수 (2,000 이하)

    static boolean breakFlag;            // 인구 이동 반복 종료 플래그 변수
    static boolean[][] visited;
    static Queue<Node> queue = new LinkedList<>();
    static List<Node> list = new ArrayList<>();        // 탐색한 연합 칸들 저장
    static int unionPopulation, unionAreaCnt;        // 연합의 총 인구 수, 연합의 나라 칸 수

    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };

    static void solution() {
        // 인구 이동이 없을 때까지 반복
        while (true) {
            breakFlag = true;                // Init
            visited = new boolean[n][n];

            for (int y = 0; y < n; y++) {
                for (int x = 0; x < n; x++) {
                    // 1) 오픈 가능한 국경선을 따라가며 연합을 탐색
                    if (!visited[y][x]) {
                        list = new ArrayList<>();

                        unionPopulation = map[y][x];
                        unionAreaCnt = 1;

                        visited[y][x] = true;
                        queue.add(new Node(y, x));
                        list.add(new Node(y, x));    // 연합에 속하는 나라 칸 추가
                        bfs();

                        // 2) 저장한 연합 칸 리스트를 통해 인구 이동 수행
                        if (list.size() > 1) {
                            movePopulation();
                            breakFlag = false;
                        }
                    }
                }
            }

            if (breakFlag)
                break;

            numOfDay++;
        }
    }

    static void bfs() {
        while (!queue.isEmpty()) {
            Node current = queue.remove();

            for (int i = 0; i < 4; i++) {
                int ny = current.y + dy[i];
                int nx = current.x + dx[i];

                if (!isValid(ny, nx) || visited[ny][nx])
                    continue;

                // 인접 나라 칸끼리 인구 차이
                int diff = Math.abs(map[current.y][current.x] - map[ny][nx]);
                if (l <= diff && diff <= r) {
                    visited[ny][nx] = true;
                    queue.add(new Node(ny, nx));
                    list.add(new Node(ny, nx));

                    unionPopulation += map[ny][nx];
                    unionAreaCnt++;
                }
            }
        }
    }

    static void movePopulation() {
        // 연합을 이루는 각 칸의 인구 수 = (연합의 총 인구 수) / (연합을 이루고 있는 칸의 수)
        int movedPopulation = unionPopulation / unionAreaCnt;

        for (Node n : list) {
            map[n.y][n.x] = movedPopulation;
        }
    }

    static boolean isValid(int y, int x) {
        return (0 <= y && y < n) && (0 <= x && x < n);
    }

    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());
        l = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution();

        System.out.println(numOfDay);
    }
}

https://www.acmicpc.net/problem/23288

1. 아이디어

• 구현, 시뮬레이션: 주사위 1칸 이동, 주사위 이동 방향 결정
• BFS: 주사위 1칸 이동 후 획득 점수 계산

1) 주사위 1칸 이동

• 이동 방향에 칸이 있는 경우, 해당 이동 방향으로 1칸 굴러감

• 이동 방향에 칸이 없는 경우, 방향을 바꾸어 반대 방향으로 1칸 굴러감 ※ diceDir 반대 방향 값으로 갱신 !!

• 주사위 굴리기 메소드: dice[], diceY, diceX 갱신 => 상, 하, 좌, 우로 각각 굴리는 메소드

  
  

2) 주사위 도착 칸 [diceY][diceX]에 대한 획득 점수 계산

• 주사위 도착 칸의 값: boardValue = map[diceY][diceX]

• BFS 수행: int bfs()

  • [diceY][diceX]의 인접 칸 값이 boardValue와 같은 경우, 탐색 확장
    

3) 다음 이동 방향 결정

• 주사위 아랫 면의 값 A, 주사위가 위치한 칸의 값 B

• A = dice[5], B = map[diceY][diceX]

• A > B인 경우, 이동 방향을 90도 시계 방향 회전

• A < B인 경우, 이동 방향을 90도 반시계 방향 회전

• A == B인 경우, 이동 방향 그대로 유지

2. 자료구조

• int[] dice: 길이 6, 주사위 전개도

• diceY, diceX, diceDir: 주사위 위치, 이동 방향

• boolean[][] visited: BFS 방문 처리

• Queue<Node>, LinkedList<Node>: BFS 수행

  • Node: 현재 탐색 위치 (y, x)

코드

import java.io.*;
import java.util.*;

class Node {
    public int y, x;

    public Node(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static int n, m;            // n x m 맵
    static int k;                // k번 이동
    static int[][] map;
    static int totalScore;        // 출력, 획득 점수

    static int[] dice = new int[6];        // 주사위 전개도 배열
    static int diceY, diceX;            // 주사위 위치
    static int diceDir;                    // 주사위 이동 방향

    static boolean[][] visited;
    static Queue<Node> queue = new LinkedList<>();
    static int[] dy = { -1, 0, 1, 0 };    // 상우하좌 (북동남서)
    static int[] dx = { 0, 1, 0, -1 };

    static void solution() {
        for (int i = 0; i < k; i++) {
            // 1) 주사위 1칸 이동
            rollDice();

            // 2) 주사위 도착 칸 [diceY][diceX]에 대한 획득 점수 계산
            visited = new boolean[n + 1][m + 1];        // Init

            visited[diceY][diceX] = true;
            queue.add(new Node(diceY, diceX));
            totalScore += bfs();

            // 3) 다음 이동 방향 결정
            changeDiceDir();
        }
    }

    static void rollDice() {
        // 현재 방향으로 이동했을 시, 다음 칸
        int ny = diceY + dy[diceDir];
        int nx = diceX + dx[diceDir];

        // 이동 방향에 칸이 있는 경우, 해당 이동 방향으로 1칸 굴러감
        if (isValid(ny, nx)) {
            if (diceDir == 0) rollDiceUp();
            else if (diceDir == 1) rollDiceRight();
            else if (diceDir == 2) rollDiceDown();
            else if (diceDir == 3) rollDiceLeft();
        }
        // 이동 방향에 칸이 없는 경우, 방향을 바꾸어 반대 방향으로 1칸 굴러감
        else {
            if (diceDir == 0) {
                diceDir = 2;
                rollDiceDown();
            }
            else if (diceDir == 1) {
                diceDir = 3;
                rollDiceLeft();
            }
            else if (diceDir == 2) {
                diceDir = 0;
                rollDiceUp();
            }
            else if (diceDir == 3) {
                diceDir = 1;
                rollDiceRight();
            }
        }
    }

    static void rollDiceLeft() {
        int[] tempDice = new int[6];
        for (int i = 0; i < 6; i++) {
            tempDice[i] = dice[i];
        }

        dice[0] = tempDice[2];
        dice[2] = tempDice[5];
        dice[3] = tempDice[0];
        dice[5] = tempDice[3];

        diceX--;
    }

    static void rollDiceRight() {
        int[] tempDice = new int[6];
        for (int i = 0; i < 6; i++) {
            tempDice[i] = dice[i];
        }

        dice[0] = tempDice[3];
        dice[2] = tempDice[0];
        dice[3] = tempDice[5];
        dice[5] = tempDice[2];

        diceX++;
    }

    static void rollDiceUp() {
        int[] tempDice = new int[6];
        for (int i = 0; i < 6; i++) {
            tempDice[i] = dice[i];
        }

        dice[0] = tempDice[4];
        dice[1] = tempDice[0];
        dice[4] = tempDice[5];
        dice[5] = tempDice[1];

        diceY--;
    }

    static void rollDiceDown() {
        int[] tempDice = new int[6];
        for (int i = 0; i < 6; i++) {
            tempDice[i] = dice[i];
        }

        dice[0] = tempDice[1];
        dice[1] = tempDice[5];
        dice[4] = tempDice[0];
        dice[5] = tempDice[4];

        diceY++;
    }

    /* 주사위 도착 위치 dicePoint를 시작 지점으로 BFS 탐색
     * - 주사위 도착 칸에 대한 획득 점수 계산 */
    static int bfs() {
        int boardValue = map[diceY][diceX];
        int cnt = 1;

        while (!queue.isEmpty()) {
            Node current = queue.remove();

            for (int i = 0; i < 4; i++) {
                int ny = current.y + dy[i];
                int nx = current.x + dx[i];

                if (!isValid(ny, nx))
                    continue;

                // 인접 칸의 값 == boardValue인 경우, 탐색 확장
                if (!visited[ny][nx] && map[ny][nx] == boardValue) {
                    visited[ny][nx] = true;
                    queue.add(new Node(ny, nx));

                    cnt++;
                }
            }
        }

        return boardValue * cnt;
    }

    /* 주사위 이동 방향 결정 */
    static void changeDiceDir() {
        int a = dice[5];                // 주사위 아랫 면의 값
        int b = map[diceY][diceX];        // 주사위가 위치한 칸의 값

        // dy, dx 순서: 상우하좌
        if (a > b) {        // A > B인 경우, 이동 방향을 90도 시계 방향 회전
            diceDir = (diceDir + 1) % 4;
        }
        else if (a < b) {    // A < B인 경우, 이동 방향을 90도 반시계 방향 회전
            diceDir = (diceDir + 3) % 4;
        }
    }

    static boolean isValid(int y, int x) {
        return (1 <= y && y <= n) && (1 <= x && x <= m);
    }

    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());
        k = Integer.parseInt(st.nextToken());

        map = new int[n + 1][m + 1];        // [1][1] ~ [n][m] 사용
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 최초 주사위 전개도
        for (int i = 0; i < 6; i++) {
            dice[i] = i + 1;
        }

        // 최초 주사위 - 위치: [1][1], 이동 방향: 동쪽(오른쪽)
        diceY = 1;
        diceX = 1;
        diceDir = 1;

        solution();

        System.out.println(totalScore);
    }
}

https://www.acmicpc.net/problem/17142

1. 아이디어

• 조합(백트래킹 + 브루트포스): 전체 k개 바이러스에서 활성화 시킬 m개 선택
• BFS: 바이러스 퍼뜨리기

1) 활성화 시킬 바이러스 m개 선택

• void backtrack(int virusIdx, int selectCnt)

• 재귀함수 종료 조건: selectCnt == m => 활성화 시킬 바이러스 m개 선택 완료한 경우

• for문으로 i = virustIdx ~ 전체 바이러스 개수만큼 반복 => 해당 [i]번 바이러스를 선택 O or 선택 X

  
  

2) 바이러스 퍼뜨리기

• 활성화 선택한 m개 바이러스를 방문 처리, 큐에 추가

• BFS 수행 (Queue가 Empty 할 때까지 반복)

  ① 인접 칸을 아직 방문 안했고, 빈 칸인 경우

  • 방문 처리 및 큐에 추가

  • emptyCnt -1 감소 처리

  ② 인접 칸을 아직 방문 안했고, 바이러스 칸인 경우

  • 방문 처리 및 큐에 추가 => 바이러스 칸 지나가기

  • ※ 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면, 비활성 바이러스가 활성으로 변함

  • emptyCnt == 0 인 경우, BFS while문 break 및 current.time + 1 반환

2. 자료구조

• int[][] map

• int emptyCnt: 빈 칸 개수 저장

• List<Node> virusList: 입력 전체 k개 바이러스 위치 저장

• boolean[] selected: 활성화 시킬 바이러스 선택 표시

• boolean[][] visited: BFS 방문 처리

• Queue<Node>, LinkedList<Node>: BFS 수행

3. 시간 복잡도

• 전체 k개 바이러스에서 m개 선택하여 조합 구성 (순서 상관 X, 중복 X) => C(k, m)

• 전체 최대 경우의 수 = C(10, 5) = 212개

코드

import java.io.*;
import java.util.*;

class Node {
    public int y, x;
    public int time;

    public Node(int y, int x, int time) {
        this.y = y;
        this.x = x;
        this.time = time;
    }
}

public class Main {
    static int n;                    // n x n 맵
    static int m;                    // 활성시킬 바이러스 m개 선택
    static int[][] map;
    static int minTime = Integer.MAX_VALUE;        // 출력

    static int emptyCnt;            // 맵에서 빈 칸 개수
    static List<Node> virusList = new ArrayList<>();    // 전체 k개 바이러스 위치
    static boolean[] selected;        // 활성화 시킬 바이러스 선택 표시

    static boolean[][] visited;
    static Queue<Node> queue = new LinkedList<>();
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static final int EMPTY = 0, WALL = 1, VIRUS = 2;

    static void backtrack(int vIdx, int selectCnt) {
        // 활성화 시킬 바이러스 m개 선택 완료한 경우
        if (selectCnt == m) {
            // minTime 갱신
            int time = spreadVirus();
            if (time != -1) {
                minTime = Math.min(minTime, time);
            }

            return;
        }

        // 활성화 시킬 바이러스 선택
        for (int i = vIdx; i < virusList.size(); i++) {
            // 선택 O
            selected[i] = true;
            backtrack(i + 1, selectCnt + 1);

            // 선택 X
            selected[i] = false;
        }
    }

    /* 바이러스 퍼뜨리기 */
    static int spreadVirus() {
        int copyEmptyCnt = emptyCnt;
        int[][] copyMap = new int[n][n];    // map copy
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                copyMap[i][j] = map[i][j];
            }
        }

        visited = new boolean[n][n];        // Init
        queue = new LinkedList<>();

        // 선택한 활성화 시킬 바이러스 칸 => 방문 처리 및 큐에 추가
        for (int vIdx = 0; vIdx < virusList.size(); vIdx++) {
            if (selected[vIdx]) {
                Node current = virusList.get(vIdx);

                visited[current.y][current.x] = true;
                queue.add(new Node(current.y, current.x, 0));
                // 활성화 시킨 바이러스 칸: 시간 0으로 설정
            }
        }

        while (!queue.isEmpty()) {
            Node current = queue.remove();

            for (int i = 0; i < 4; i++) {
                int ny = current.y + dy[i];
                int nx = current.x + dx[i];

                if (!isValid(ny, nx) || visited[ny][nx])
                    continue;

                // 인접 칸이 빈 칸인 경우, 바이러스 퍼뜨림
                if (copyMap[ny][nx] == EMPTY) {
                    visited[ny][nx] = true;
                    queue.add(new Node(ny, nx, current.time + 1));

                    copyEmptyCnt--;
                }
                // 인접 칸이 바이러스 칸인 경우, 지나감
                // => 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면, 비활성 바이러스가 활성으로 변함
                else if (copyMap[ny][nx] == VIRUS) {
                    visited[ny][nx] = true;
                    queue.add(new Node(ny, nx, current.time + 1));
                }

                if (copyEmptyCnt == 0)
                    return current.time + 1;
            }
        }

        return -1;
    }

    static boolean isValid(int y, int x) {
        return (0 <= y && y < n) && (0 <= x && x < n);
    }

    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][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (map[i][j] == EMPTY) {
                    emptyCnt++;
                }
                else if (map[i][j] == VIRUS) {
                    virusList.add(new Node(i, j, VIRUS));
                }
            }
        }

        // 예외 처리: 기존 빈 칸이 없는 경우, 출력 0초
        if (emptyCnt == 0) {
            System.out.println(0);
            return;
        }

        selected = new boolean[virusList.size()];
        backtrack(0, 0);

        if (minTime == Integer.MAX_VALUE) {
            System.out.println(-1);
        }
        else {
            System.out.println(minTime);
        }
    }
}

https://www.acmicpc.net/problem/14501

1. 아이디어

• 조합(백트래킹 + 브루트 포스)

• 백트래킹 종료 조건: depth == n + 1 => 상담 정보를 모두 확인한 경우

• 현재 상태에서 상담 가능한 경우 => 선택 O or X

2. 자료구조

• int[] t, int[] p: 입력 상담 정보

3. 시간 복잡도

• 1개 상담에 대해 선택 O / X 하는 2가지 경우 존재

• 전체 n개 상담에 대한 최대 경우의 수 = 2^n => n 최대값 대입: 2^15 = 32,768

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n;                // 남은 n일
    static int[] t;
    static int[] p;
    static int maxMoney;        // 출력

    /* day: 상담 진행 시작 가능한 일자 */
    static void backtrack(int day, int money) {
        // 마지막 일자의 상담 정보까지 모두 확인한 경우
        if (day == n + 1) {
            maxMoney = Math.max(maxMoney, money);
            return;
        }

        // 선택 O
        if (day + t[day] <= n + 1) {
            backtrack(day + t[day], money + p[day]);
        }

        // 선택 X
        backtrack(day + 1, money);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        t = new int[n + 1];        // [1] ~ [n] 사용
        p = new int[n + 1];        // [1] ~ [n] 사용
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());

            t[i] = Integer.parseInt(st.nextToken());
            p[i] = Integer.parseInt(st.nextToken());
        }

        backtrack(1, 0);        // Init Call

        System.out.println(maxMoney);
    }
}

https://www.acmicpc.net/problem/20055

1. 아이디어

• 구현, 시뮬레이션

• 로봇: 컨베이어 벨트 윗 부분에서만 위치 => 벨트 칸 [1]번 ~ [n]번
  

1) 벨트가 각 칸에 있는 로봇과 함께 1칸 회전

• void rotate()

  • a[], existRobot[] 벨트 회전 시계 방향으로 1칸씩 이동

• rotate() 수행 후, [n]번 칸에 로봇 있으면, 해당 로봇 삭제 (로봇 내림)

  
  

2) 가장 먼저 벨트에 올라간 로봇부터, 벨트 회전 방향으로 1칸 이동 가능한 경우 이동

• "가장 먼저 벨트에 올라간 로봇부터"

  • for문으로 [n-1] ~ [1] 순서로 확인

    로봇은 컨베이어 벨트 윗 부분에만 위치 + [n]번 칸의 로봇은 삭제됨 (로봇 내림 처리)

  • [i] 칸 기준: [i+1] 칸에 로봇이 없고 [i+1] 칸의 내구도 >= 1인 경우 => [i+1] 칸으로 이동

• for문으로 이동 수행 완료 후, [n]번 칸에 로봇 있으면, 해당 로봇 삭제 (로봇 내림)

  
  

3) [1]번 칸 내구도 > 0 인 경우, [1]번 칸에 로봇을 올림

• [1]번 칸에 로봇 올리고, 내구도 감소 처리
  

4) 내구도가 0인 칸의 개수 >= k 인 경우, 과정 종료

• for문으로 전체 벨트 칸의 내구도 확인

2. 자료구조

• int[] a: 각 벨트 칸의 내구도

• boolean[] existRobot: 각 벨트 칸에 로봇이 존재하는지 표시

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n;                    // 길이 2 x n 벨트
    static int k;
    static int[] a;                    // 각 벨트 칸의 내구도
    static boolean[] existRobot;
    static int cnt;                    // 출력, 종료 시 과정을 몇 번째 반복 중이였는지

    static void solution() {
        cnt = 1;

        while (true) {
            // 1) 벨트가 각 칸에 있는 로봇과 함께 1칸 회전
            rotate();
            existRobot[n] = false;    // [n]번 칸에 로봇 있으면, 해당 로봇 삭제(로봇 내림)

            // 2) 가장 먼저 올라간 로봇부터, 이동 가능한 로봇들 이동
            moveAllRobots();
            existRobot[n] = false;    // [n]번 칸에 로봇 있으면, 해당 로봇 삭제(로봇 내림)

            // 3) [1]번 칸 내구도 > 0 인 경우, [1]번 칸에 로봇을 올림
            if (a[1] > 0) {
                // [1]번 칸에 로봇 올리고, 내구도 감소 처리
                existRobot[1] = true;
                a[1]--;
            }

            // 4) 내구도가 0인 벨트 칸의 개수 >= k 인 경우, 과정 종료
            if (countZeroDurability() >= k) {
                break;
            }

            cnt++;
        }
    }

    /* 벨트 회전: 각 벨트 칸, 로봇 1칸씩 시계 방향으로 이동 */
    static void rotate() {
        int tempA = a[2*n];
        for (int i = 2 * n; i >= 2; i--) {
            a[i] = a[i-1];
        }
        a[1] = tempA;

        for (int i = n; i >= 2; i--) {
            existRobot[i] = existRobot[i-1];
        }
        existRobot[1] = false;        // [1]번 칸에는 로봇이 없게됨
    }

    /* 이동 가능한 로봇들 이동 */
    static void moveAllRobots() {
        for (int i = n - 1; i >= 1; i--) {
            // [i]번 칸에 로봇 존재하는 경우: [i]번 칸의 로봇을 다음 칸으로 이동 가능한지 확인
            if (existRobot[i]) {
                // [i+1]번 칸에 로봇이 없고, [i+1]번 칸의 내구도가 1 이상인 경우
                if (!existRobot[i+1] && a[i+1] >= 1) {
                    // [i]번 칸의 로봇을 [i+1]번 칸으로 이동
                    existRobot[i] = false;
                    existRobot[i+1] = true;
                    a[i+1]--;
                }
            }
        }
    }

    /* 내구도 0인 벨트 칸 개수 반환 */
    static int countZeroDurability() {
        int cnt = 0;

        for (int i = 1; i <= 2 * n; i++) {
            if (a[i] == 0)
                cnt++;
        }

        return cnt;
    }

    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());
        k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        a = new int[2 * n + 1];                    // [1] ~ [2*n] 사용
        existRobot = new boolean[n + 1];        // [1] ~ [n] 사용: 로봇은 컨베이어 벨트 윗 부분에만 존재
        for (int i = 1; i <= 2 * n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        solution();

        System.out.println(cnt);
    }
}

https://www.acmicpc.net/problem/19237

1. 아이디어

• 시뮬레이션, 구현

• 초기: 모든 상어들이 본인 시작 위치에서 자신의 냄새를 뿌림
  

다음을 상어가 1마리만 남을 때까지 반복

• 남은 1마리 상어 = 1번 상어 => 가장 강한 상어
  

1) 각 상어 이동

① 인접 칸 중, 냄새가 없는 칸이 존재하는 경우

• 해당 냄새가 없는 칸으로 이동
• 냄새가 없는 칸이 여러 개일 경우, 상어의 방향 우선순위를 따름

② 인접 칸에 모두 냄새가 있는 경우

• 자신의 냄새가 있는 칸으로 이동
• 자신의 냄새 칸이 여러 개일 경우, 상어의 방향 우선순위를 따름
  

2) 같은 칸에 있는 상어들은 1마리만 남기기

3) 이전 냄새 감소 처리

• 2중 for문으로 smellMap[][] 확인

• smellMap[i][j].smellCnt > 0인 경우, smellMap[i][j].smellCnt - 1 처리

• 감소한 smellMap[i][j].smellCnt == 0인 경우, smellMap[i][j].sharkIdx = 0 처리

  
  

4) 새로 이동한 위치에 냄새 뿌리기

2. 자료구조

• int[][][] preferDirs: 각 상어의 보고있는 방향 별, 이동 방향 우선순위

  • ex) preferDirs[상어 번호][현재 보고있는 방향][이동 방향 우선순위: 1 ~ 4]

• Smell[][] smellMap: 각 위치 별, 각 상어가 남긴 냄새 양 표시

  • Smell: 상어 번호 sharkIdx, 상어가 남긴 냄새 양 smellCnt

• Shark[] sharks: 각 상어의 위치 (y, x), 방향 dir

코드

import java.io.*;
import java.util.*;

class Smell {
    public int sharkIdx;        // 냄새를 남긴 상어의 번호
    public int smellCnt;        // 남은 냄새 양

    public Smell(int sharkIdx, int smellCnt) {
        this.sharkIdx = sharkIdx;
        this.smellCnt = smellCnt;
    }
}

class Shark {
    public int y, x;
    public int dir;

    public Shark(int y, int x, int dir) {
        this.y = y;
        this.x = x;
        this.dir = dir;
    }
}

public class Main {
    static int n;                // n x n 맵
    static int m;                // 1번 ~ m번 상어
    static int k;                // 상어가 k번 이동하면, 냄새 사라짐
    static int time;            // 출력, 1번 상어만 남는 데 걸리는 시간
    static boolean finished;    // 성공 및 종료 여부

    static Smell[][] smellMap;
    static int[][][] preferDirs;    // 각 상어의 보고있는 방향 별, 이동 방향 우선순위
    static Shark[] sharks;            // 각 상어의 위치, 방향
    static int numOfShark;            // 남은 상어 수

    // [1] ~ [4] 사용: 상하좌우
    static int[] dy = { 0, -1, 1, 0, 0 };
    static int[] dx = { 0, 0, 0, -1, 1 };

    static void solution() {
        // 초기: 모든 상어들이 본인 시작 위치에서 자신의 냄새를 뿌림
        for (int sharkIdx = 1; sharkIdx <= m; sharkIdx++) {
            spreadSmell(sharkIdx);
        }

        // 상어 이동, 냄새 처리 반복
        while (time < 1000) {
            // 1) 각 상어 이동
            for (int sharkIdx = 1; sharkIdx <= m; sharkIdx++) {
                // 쫓겨나지 않고 남은 상어인 경우, 상어 이동
                if (sharks[sharkIdx] != null) {
                    moveShark(sharkIdx);
                }
            }

            // 같은 칸에 위치한 상어들은 1마리만 남기기
            removeDuplicateSharks();

            // 2) 이전 냄새 감소 처리
            decreaseSmell();

            // 3) 새로 이동한 위치에 냄새 뿌리기
            for (int sharkIdx = 1; sharkIdx <= m; sharkIdx++) {
                // 쫓겨나지 않고 남은 상어인 경우, 새로 이동한 자리에 냄새 뿌림
                if (sharks[sharkIdx] != null) {
                    spreadSmell(sharkIdx);
                }
            }

            time++;

            if (numOfShark == 1) {
                finished = true;
                break;
            }
        }
    }

    /* Shark[] sharks에 상어 이동 위치, 방향 저장 */
    static void moveShark(int sharkIdx) {
        Shark s = sharks[sharkIdx];

        // 인접 칸 확인 - 우선순위에 따라 확인
        for (int i = 1; i <= 4; i++) {
            int preferDir = preferDirs[sharkIdx][s.dir][i];

            int ny = s.y + dy[preferDir];
            int nx = s.x + dx[preferDir];

            if (!isValid(ny, nx))
                continue;

            // 인접 방향에 냄새가 없는 경우 => 해당 방향으로 이동
            if (smellMap[ny][nx].smellCnt == 0) {
                sharks[sharkIdx].y = ny;
                sharks[sharkIdx].x = nx;
                sharks[sharkIdx].dir = preferDir;

                return;
            }
        }

        // 인접 방향에 모두 냄새가 있는 경우
        // 자신의 냄새가 있는 칸들 중, 방향 우선순위에 따라 이동
        for (int i = 1; i <= 4; i++) {
            int preferDir = preferDirs[sharkIdx][s.dir][i];

            int ny = s.y + dy[preferDir];
            int nx = s.x + dx[preferDir];

            if (!isValid(ny, nx))
                continue;

            // 우선순위에 따른 인접 방향에 자신의 냄새가 있는 경우 => 해당 방향으로 이동
            if (smellMap[ny][nx].sharkIdx == sharkIdx) {
                sharks[sharkIdx].y = ny;
                sharks[sharkIdx].x = nx;
                sharks[sharkIdx].dir = preferDir;

                break;
            }
        }
    }

    static void removeDuplicateSharks() {
        // 같은 칸에 위치한 상어들은 1마리만 남기기
        int[][] sharkMap = new int[n + 1][n + 1];

        // 가장 강한 1번 상어부터 확인
        for (int sharkIdx = 1; sharkIdx <= m; sharkIdx++) {
            Shark s = sharks[sharkIdx];
            if (s == null)        // 이미 쫓겨난 상어
                continue;

            if (sharkMap[s.y][s.x] == 0) {        // 빈 칸인 경우
                sharkMap[s.y][s.x] = sharkIdx;
            }
            else {        // 이미 sharkIdx번 상어보다 강한 상어가 존재하는 경우
                sharks[sharkIdx] = null;        // sharkIdx번 상어 내보냄
                numOfShark--;
            }
        }
    }

    static void decreaseSmell() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (smellMap[i][j].smellCnt > 0) {
                    smellMap[i][j].smellCnt--;
                    smellMap[i][j].sharkIdx = (smellMap[i][j].smellCnt > 0) ?
                            smellMap[i][j].sharkIdx : 0;
                }
            }
        }
    }

    static void spreadSmell(int sharkIdx) {
        Shark s = sharks[sharkIdx];
        smellMap[s.y][s.x].sharkIdx = sharkIdx;
        smellMap[s.y][s.x].smellCnt = k;
    }

    static boolean isValid(int y, int x) {
        return (1 <= y && y <= n) && (1 <= x && x <= n);
    }

    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());
        k = Integer.parseInt(st.nextToken());

        numOfShark = m;

        smellMap = new Smell[n + 1][n + 1];
        sharks = new Shark[m + 1];        // [1] ~ [m] 사용
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= n; j++) {
                int sharkIdx = Integer.parseInt(st.nextToken());
                smellMap[i][j] = new Smell(sharkIdx, 0);

                if (sharkIdx >= 1) {
                    sharks[sharkIdx] = new Shark(i, j, 0);        // dir: 일단 0 초기화
                }
            }
        }

        // 각 상어의 초기 방향
        st = new StringTokenizer(br.readLine());
        for (int sharkIdx = 1; sharkIdx <= m; sharkIdx++) {
            sharks[sharkIdx].dir = Integer.parseInt(st.nextToken());
        }

        // 각 상어의 보고있는 방향 별, 이동 방향 우선순위: [1][1][1] ~ [m][4][4] 사용
        preferDirs = new int[m + 1][5][5];
        for (int sharkIdx = 1; sharkIdx <= m; sharkIdx++) {
            for (int watchDir = 1; watchDir <= 4; watchDir++) {
                st = new StringTokenizer(br.readLine());

                for (int preferRank = 1; preferRank <= 4; preferRank++) {
                    preferDirs[sharkIdx][watchDir][preferRank] = Integer.parseInt(st.nextToken());
                }
            }
        }

        solution();

        if (finished) {
            System.out.println(time);
        }
        else {
            System.out.println(-1);
        }
    }
}

https://www.acmicpc.net/problem/17140

1. 아이디어

• 구현, 시뮬레이션
• 정렬

• R 연산: 배열의 열 개수 변동 가능

• C 연산: 배열의 행 개수 변동 가능

2. 자료구조

• int[][] arr: 실사용 크기 100 x 100으로 할당해서 사용

• PriorityQueue<Pair>: 한 행 or 열 정렬 ※ Pair: 숫자 number, 해당 숫자의 등장 횟수 cnt

코드

import java.io.*;
import java.util.*;

class Pair implements Comparable<Pair> {
    public int number, cnt;        // 숫자 number의 등장 횟수 cnt

    public Pair(int number, int cnt) {
        this.number = number;
        this.cnt = cnt;
    }

    // 숫자의 등장 횟수 작은 순 -> 숫자 작은 순
    public int compareTo(Pair o) {
        if (this.cnt != o.cnt)
            return this.cnt - o.cnt;
        return this.number - o.number;
    }
}

public class Main {
    static int r, c, k;            // 목표: arr[r][c] == k
    static int minTime;            // 출력

    static int[][] arr = new int[101][101];        // [1][1] ~ 최대 [100][100] 사용
    static int sizeRow = 3, sizeCol = 3;        // 배열의 행, 열 크기
    static Map<Integer, Integer> hashMap = new HashMap<>();            // 각 숫자의 등장 횟수 count
    static PriorityQueue<Pair> pq = new PriorityQueue<>();
    static boolean finished;

    static void solution() {
        while (minTime <= 100) {
            // 목표 조건 만족하는지 확인
            if (arr[r][c] == k) {
                finished = true;
                break;
            }

            if (sizeRow >= sizeCol) {
                operationR();
            }
            else {
                operationC();
            }

            minTime++;
        }

        if (!finished) {
            minTime = -1;
        }
    }

    /* 행 기준으로 정렬 */
    static void operationR() {
        int[][] tempArr = new int[101][101];
        sizeCol = 0;        // R 연산은 열 개수 변동 가능 (밑에 코드에서 갱신)

        for (int y = 1; y <= 100; y++) {
            hashMap.clear();

            for (int x = 1; x <= 100; x++) {
                int number = arr[y][x];
                if (number == 0)        // 0은 제외
                    continue;

                // 각 숫자의 등장 횟수를 hashMap에 저장
                if (!hashMap.containsKey(number)) {
                    hashMap.put(number, 1);
                }
                else {
                    int cnt = hashMap.get(number);
                    hashMap.put(number, cnt + 1);
                }
            }

            // 행에서 각 숫자와 해당 숫자의 등장 횟수를 pq에 저장 및 정렬
            for (int number : hashMap.keySet()) {
                int cnt = hashMap.get(number);
                pq.add(new Pair(number, cnt));
            }

            // 배열의 해당 행에 정렬 결과 저장
            // 배열의 열 개수 갱신
            int x = 1;
            while (!pq.isEmpty()) {
                Pair p = pq.remove();
                tempArr[y][x++] = p.number;
                tempArr[y][x++] = p.cnt;
            }
            sizeCol = Math.max(sizeCol, x - 1);
        }

        arr = tempArr;
    }

    /* 열 기준으로 정렬 */
    static void operationC() {
        int[][] tempArr = new int[101][101];
        sizeRow = 0;        // C 연산은 행 개수 변동 가능 (밑에 코드에서 갱신)

        for (int x = 1; x <= 100; x++) {
            hashMap.clear();

            for (int y = 1; y <= 100; y++) {
                int number = arr[y][x];
                if (number == 0)        // 0은 제외
                    continue;

                // 각 숫자의 등장 횟수를 hashMap에 저장
                if (!hashMap.containsKey(number)) {
                    hashMap.put(number, 1);
                }
                else {
                    int cnt = hashMap.get(number);
                    hashMap.put(number, cnt + 1);
                }
            }

            // 열에서 각 숫자와 해당 숫자의 등장 횟수를 pq에 저장 및 정렬
            for (int number : hashMap.keySet()) {
                int cnt = hashMap.get(number);
                pq.add(new Pair(number, cnt));
            }

            // 배열의 해당 열에 정렬 결과 저장
            // 배열의 행 개수 갱신
            int y = 1;
            while (!pq.isEmpty()) {
                Pair p = pq.remove();
                tempArr[y++][x] = p.number;
                tempArr[y++][x] = p.cnt;
            }
            sizeRow = Math.max(sizeRow, y - 1);
        }

        arr = tempArr;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= 3; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution();

        System.out.println(minTime);
    }
}

https://www.acmicpc.net/problem/17144

1. 아이디어

구현, 시뮬레이션

1) 모든 미세먼지 칸에서 동시에 미세먼지 확산

• tempMap[][]에 map[][]을 copy

• 2중 for문으로 tempMap[][] 확인

• tempMap[i][j]에 미세먼지가 존재하는 경우, 인접 방향으로 미세먼지 확산시킴

  • map[][]에 확산 처리

  • map[i][j]에는 확산시킨 양을 빼줌

    
    

2) 공기 청정기 작동

• 위쪽 공기 청정기 바람: 반시계 방향으로 순환

• 아래쪽 공기 청정기 바람: 시계 방향으로 순환

• 바람이 불면, 미세먼지가 바람의 방향으로 모두 1칸씩 이동

• 공기 청정기로 들어간 미세먼지는 모두 정화됨

코드

import java.io.*;
import java.util.*;

public class Main {
    static int r, c;                // r x c 행렬
    static int t;                    // t초 후
    static int[][] map;
    static int sum;                    // 출력

    static int[] machineY = new int[2];        // 공기 청정기 위치
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static final int MACHINE = -1;

    static void solution() {
        for (int i = 0; i < t; i++) {
            // 1) 모든 미세먼지 칸에서 동시에 미세먼지 확산
            spreadAllDusts();

            // 2) 공기 청정기 작동
            runMachine();
        }

        // 남은 미세먼지 양 계산
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                if (map[i][j] > 0)
                    sum += map[i][j];
            }
        }
    }

    static void spreadAllDusts() {
        int[][] tempMap = new int[r + 1][c + 1];        // map copy
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                tempMap[i][j] = map[i][j];
            }
        }

        for (int y = 1; y <= r; y++) {
            for (int x = 1; x <= c; x++) {
                // tempMap[i][j]에 미세먼지 존재하는 경우
                if (tempMap[y][x] > 0) {
                    // 인접 방향으로 미세먼지 확산시킴: map[][]에 확산 처리
                    int amount = tempMap[y][x] / 5;        // 인접 1칸에 확산되는 양

                    // 인접한 4개 칸 확인
                    for (int i = 0; i < 4; i++) {
                        int ny = y + dy[i];
                        int nx = x + dx[i];

                        // 인접 칸이 공기 청정기 칸 or 범위를 벗어난 경우
                        if (!isValid(ny, nx) || tempMap[ny][nx] == MACHINE)
                            continue;

                        map[ny][nx] += amount;
                        map[y][x] -= amount;
                    }
                }
            }
        }
    }

    static void runMachine() {
        circulateUp();
        circulateDown();
    }

    /* 위쪽 공기 청정기 바람: 반시계 방향 순환 */
    static void circulateUp() {
        int mUpY = machineY[0];

        // 공기 청정기로 들어오는 바람 = 첫 열에서 아래로 내려가는 바람: 아래로 shift
        for (int y = mUpY - 1; y >= 2; y--) {
            map[y][1] = map[y-1][1];
        }

        // 맨 윗행에서 왼쪽으로 부는 바람: 왼쪽으로 shift
        for (int x = 1; x <= c - 1; x++) {
            map[1][x] = map[1][x+1];
        }

        // 끝 열에서 위로 올라가는 바람: 위로 shift
        for (int y = 1; y <= mUpY - 1; y++) {
            map[y][c] = map[y+1][c];
        }

        // 공기 청정기에서 나가는 바람 = 공기 청정기에서 오른쪽으로 부는 바람: 오른쪽으로 shift
        for (int x = c; x >= 3; x--) {
            map[mUpY][x] = map[mUpY][x-1];
        }
        map[mUpY][2] = 0;
    }

    /* 아래쪽 공기 청정기 바람: 시계 방향 순환 */
    static void circulateDown() {
        int mDownY = machineY[1];

        // 공기 청정기로 들어오는 바람 = 첫 열에서 위로 올가는 바람: 위로 shift
        for (int y = mDownY + 1; y <= r - 1; y++) {
            map[y][1] = map[y+1][1];
        }

        // 맨 아래 행에서 왼쪽으로 부는 바람: 왼쪽으로 shift
        for (int x = 1; x <= c - 1; x++) {
            map[r][x] = map[r][x+1];
        }

        // 끝 열에서 아래로 내려가는 바람: 아래로 shift
        for (int y = r; y >= mDownY + 1; y--) {
            map[y][c] = map[y-1][c];
        }

        // 공기 청정기에서 나가는 바람 = 공기 청정기에서 오른쪽으로 부는 바람: 오른쪽으로 shift
        for (int x = c; x >= 3; x--) {
            map[mDownY][x] = map[mDownY][x-1];
        }
        map[mDownY][2] = 0;
    }

    static boolean isValid(int y, int x) {
        return (1 <= y && y <= r) && (1 <= x && x <= c);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        int machineIdx = 0;
        map = new int[r + 1][c + 1];            // [1][1] ~ [r][c] 사용
        for (int i = 1; i <= r; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= c; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (map[i][j] == MACHINE) {
                    machineY[machineIdx++] = i;
                }
            }
        }

        solution();

        System.out.println(sum);
    }
}

https://www.acmicpc.net/problem/15684

1. 아이디어

• 구현, 시뮬레이션
• 조합(백트래킹 + 브루트 포스)

2. 자료구조

• int[][] map: 가로선 연결 정보 맵

  • 가로선 연결 표시: map[i][j] = 1, map[i][j+1] = 2

• boolean finished

3. 시간 복잡도

• 추가할 수 있는 가로선 최대 개수 = (n-1) x h (입력 가로선이 0개일 때) => n, h 최대값 대입: 최대 270개

• 추가한 가로선이 3개 초과하면, 출력 -1로 더 확인할 필요 X => 추가할 가로선 0개, 1개, 2개, 3개로 제한하여, 각각 조합 구성 및 탐색

• 최대 확인할 경우의 수 = C(270, 0) + C(270, 1) + C(270, 2) + C(270, 3)

     = 1 + 270 + 36,315 + 3,244,140 = 3,280,726

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;                // n개 세로선, m개 가로선
    static int h;                    // 세로선마다 가로선을 놓을 수 있는 위치 h개
    static int minCnt = -1;            // 출력, 추가하는 가로선 개수 최소값

    static int[][] map;                // 가로선 연결 정보 맵
    static boolean finished;
    static final int EMPTY = 0, RIGHT = 1, LEFT = 2;

    /* addedCnt: 현재까지 추가한 가로선 개수, finishCnt: 미리 정한 추가할 가로선 개수 */
    static void backtrack(int y, int x, int addedCnt, int finishCnt) {
        // 이전 분기에서 목표 조건 만족한 경우, 다른 분기 확인 X
        if (finished)
            return;

        // 미리 정한 추가할 가로선 개수만큼 가로선 추가 완료한 경우
        if (addedCnt == finishCnt) {
            // 현재까지 추가한 가로선들로 목표 조건 만족하는지 확인
            if (checkAllVLines()) {
                finished = true;
            }

            return;
        }

        // 목표 조건 불만족한 경우, 가로선 더 추가
        for (int i = y; i <= h; i++) {
            for (int j = x; j < n; j++) {
                // 가로선이 없는 경우 (가로선 추가 가능한 경우)
                if (map[i][j] == EMPTY && map[i][j+1] == EMPTY) {
                    int nx = (x + 1 < n) ? x + 1 : 1;
                    int ny = (nx == 1) ? y + 1 : y;

                    // 선택 O
                    map[i][j] = RIGHT;
                    map[i][j+1] = LEFT;
                    backtrack(ny, nx, addedCnt + 1, finishCnt);

                    // 선택 X - 복구
                    map[i][j] = EMPTY;
                    map[i][j+1] = EMPTY;
                }
            }
        }
    }

    static boolean checkAllVLines() {
        // 세로선 [1]번 ~ [n]번 차례로 확인
        for (int vLineIdx = 1; vLineIdx <= n; vLineIdx++) {
            // 세로선 1개라도 조건 만족 안되면, 실패
            if (!checkVLines(vLineIdx))
                return false;
        }

        return true;
    }

    static boolean checkVLines(int vLineIdx) {
        int vIdx = vLineIdx;    // 세로선 위치
        int hIdx = 1;            // 가로선 위치: 1칸씩 아래로 내려감

        while (hIdx <= h) {
            if (map[hIdx][vIdx] == RIGHT)
                vIdx++;
            else if (map[hIdx][vIdx] == LEFT)
                vIdx--;

            hIdx++;
        }

        return vIdx == vLineIdx;
    }

    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());
        h = Integer.parseInt(st.nextToken());

        map = new int[h + 1][n + 1];            // [1][1] ~ [h][n] 사용
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // map[a][b], map[a][b + 1] 연결한 가로선
            map[a][b] = RIGHT;
            map[a][b+1] = LEFT;
        }

        // 추가할 가로선 개수 0 ~ 3개 제한하여 탐색
        // => 추가할 가로선 개수를 미리 정하여 종료 조건으로 걸어두고 탐색
        for (int finishCnt = 0; finishCnt <= 3; finishCnt++) {
            backtrack(1, 1, 0, finishCnt);        // Init Call

            if (finished) {
                minCnt = finishCnt;
                break;
            }
        }

        System.out.println(minCnt);
    }
}

https://www.acmicpc.net/problem/14891

1. 아이디어

구현, 시뮬레이션

1) 각 톱니바퀴 회전 여부 및 회전 방향 결정

• [i]번 톱니바퀴 회전 ① [i-1]번 톱니바퀴 확인: gears[i][6]과 gears[i-1][2] 비교 ② [i+1]번 톱니바퀴 확인: gears[i][2]과 gears[i+1][6] 비교

• 각 톱니바퀴의 회전 여부, 회전 방향을 rotateDirs[]에 저장

  
  

2) 저장된 rotateDirs[]에 따라, 회전시킬 톱니바퀴 회전

① 시계 방향 회전

• gears[gearIdx][]를 오른쪽으로 shift

② 반시계 방향 회전

• gears[gearIdx][]를 왼쪽으로 shift

2. 자료구조

• int[][] gears: 각 톱니바퀴의 톱니 상태 => gears[i]: [i]번 톱니바퀴의 톱니 상태

• Command[] commands: 입력 회전 명령 ※ Command: 톱니바퀴 번호 gearIdx, 회전 방향 rotateDir

• int[] rotateDirs: 각 톱니바퀴 회전 여부 및 회전 방향 저장

코드

import java.io.*;
import java.util.*;

class Command {
    public int gearIdx;            // 톱니바퀴 번호
    public int rotateDir;        // 회전 방향

    public Command(int gearIdx, int rotateDir) {
        this.gearIdx = gearIdx;
        this.rotateDir = rotateDir;
    }
}

public class Main {
    static int[][] gears;                // 각 톱니바퀴의 톱니 상태
    static int k;                        // 톱니바퀴 회전 횟수
    static Command[] commands;            // 입력 회전 명령
    static int scores;

    static boolean[] visited;
    static int[] rotateDirs;
    static final int N = 0, S = 1;
    static final int CLOCK = 1, COUNTER_CLOCK = -1;        // 회전 방향

    static void solution() {
        for (Command command : commands) {
            // 1) 각 톱니바퀴 회전 여부 및 회전 방향 확인
            visited = new boolean[5];        // Init
            rotateDirs = new int[5];

            visited[command.gearIdx] = true;
            rotateDirs[command.gearIdx] = command.rotateDir;
            checkRotate(command.gearIdx, command.rotateDir);

            // 2) 체크한 rotateDirs[]에 따라, 회전시킬 톱니바퀴 회전
            for (int gearIdx = 1; gearIdx <= 4; gearIdx++) {
                if (rotateDirs[gearIdx] == CLOCK) {
                    rotateClock(gearIdx);
                }
                else if (rotateDirs[gearIdx] == COUNTER_CLOCK) {
                    rotateCounterClock(gearIdx);
                }
            }
        }

        // k번 회전 끝난 후, 점수 계산
        if (gears[1][0] == S) scores += 1;
        if (gears[2][0] == S) scores += 2;
        if (gears[3][0] == S) scores += 4;
        if (gears[4][0] == S) scores += 8;
    }

    /* gearIdx번 톱니바퀴가 rotateDir 방향으로 회전할 경우,
    양 옆 톱니바퀴 회전 여부 및 방향 체크 */
    static void checkRotate(int gearIdx, int rotateDir) {
        int leftGearIdx = gearIdx - 1;
        int rightGearIdx = gearIdx + 1;
        // 양 옆 톱니바퀴가 회전한다면, 회전 방향은 반대가 됨
        int otherRotateDir = (rotateDir == CLOCK) ? COUNTER_CLOCK : CLOCK;

        if (leftGearIdx >= 1 && !visited[leftGearIdx] &&
                gears[gearIdx][6] != gears[leftGearIdx][2]) {
            visited[leftGearIdx] = true;
            rotateDirs[leftGearIdx] = otherRotateDir;
            checkRotate(leftGearIdx, otherRotateDir);
        }

        if (rightGearIdx <= 4 && !visited[rightGearIdx] &&
                gears[gearIdx][2] != gears[rightGearIdx][6]) {
            visited[rightGearIdx] = true;
            rotateDirs[rightGearIdx] = otherRotateDir;
            checkRotate(rightGearIdx, otherRotateDir);
        }
    }

    /* gearIdx번 톱니바퀴를 시계 방향으로 회전 */
    static void rotateClock(int gearIdx) {
        // gears[gearIdx][]를 오른쪽으로 shift
        int temp = gears[gearIdx][7];
        for (int i = 7; i > 0; i--) {
            gears[gearIdx][i] = gears[gearIdx][i - 1];
        }
        gears[gearIdx][0] = temp;
    }

    /* gearIdx번 톱니바퀴를 반시계 방향으로 회전 */
    static void rotateCounterClock(int gearIdx) {
        // gears[gearIdx][]를 왼쪽으로 shift
        int temp = gears[gearIdx][0];
        for (int i = 0; i < 7; i++) {
            gears[gearIdx][i] = gears[gearIdx][i + 1];
        }
        gears[gearIdx][7] = temp;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer st;

        gears = new int[5][8];            // [1] ~ [4] 사용
        for (int i = 1; i <= 4; i++) {
            String input = br.readLine();

            for (int j = 0; j < 8; j++) {
                gears[i][j] = Character.getNumericValue(input.charAt(j));
            }
        }

        k = Integer.parseInt(br.readLine());

        commands = new Command[k];
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int gearIdx = Integer.parseInt(st.nextToken());
            int rotateDir = Integer.parseInt(st.nextToken());

            commands[i] = new Command(gearIdx, rotateDir);
        }

        solution();

        System.out.println(scores);
    }
}

https://www.acmicpc.net/problem/15686

1. 아이디어

• 구현, 시뮬레이션
• 조합(백트래킹 + 브루트 포스): 폐업하지 않고 남길 치킨 집 m개 선택

1) m개 치킨 집 선택

• 치킨 집을 많이 남길수록(폐업시키는 치킨 집이 적을수록) 도시의 치킨 거리가 최소가 됨 => 최대 m개 선택 (m개 이하 선택) => 정확히 m개 선택
  

2) 도시의 치킨 거리 계산

• 2중 for문으로 전체 집, 선택한 치킨 집 각각 거리 계산하여 최소 거리 찾기

2. 자료구조

• ArrayList<Pair> homeList: 전체 집 위치 저장

• ArrayList<Pair> chickenList: 전체 치킨 집 위치 저장

• boolean[] selected: 선택한 치킨 집 표시

3. 시간 복잡도

• 치킨 집 개수 최대 13개 중, m개 선택하여 조합 구성: C(13, m) => 최대 C(13, 6) or C(13, 7) = 최대 1,716개 경우의 수

코드

import java.io.*;
import java.util.*;

class Pair {
    public int y, x;

    public Pair(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static int n;                    // n x n 행렬
    static int m;                    // 선택하여 남길 치킨 집 최대 m개
    static int minSumDist = Integer.MAX_VALUE;        // 출력

    static List<Pair> homeList = new ArrayList<>();            // 전체 집
    static List<Pair> chickenList = new ArrayList<>();        // 전체 치킨 집
    static boolean[] selected;        // 선택한 치킨 집 표시
    static final int EMPTY = 0, HOME = 1, CHICKEN = 2;

    /* chickenIdx: 치킨 집 선택 시작 index, selectCnt: 현재까지 선택한 치킨 집 개수 */
    static void backtrack(int chickenIdx, int selectCnt) {
        // 치킨 집 m개 선택 완료한 경우
        if (selectCnt == m) {
            int sumDist = 0;

            for (Pair home : homeList) {
                int minDist = Integer.MAX_VALUE;        // home과 가장 가까운 치킨 집과의 치킨 거리

                for (int i = 0; i < chickenList.size(); i++) {
                    if (selected[i]) {        // 선택된 치킨 집인 경우
                        minDist = Math.min(minDist, calcDist(home, chickenList.get(i)));
                    }
                }

                sumDist += minDist;
            }

            minSumDist = Math.min(minSumDist, sumDist);
            return;
        }

        // 치킨 집 선택
        for (int i = chickenIdx; i < chickenList.size(); i++) {
            selected[i] = true;            // 선택 O
            backtrack(i + 1, selectCnt + 1);

            selected[i] = false;        // 선택 X - 복구
        }
    }

    static int calcDist(Pair home, Pair chicken) {
        return Math.abs(home.y - chicken.y) + Math.abs(home.x - chicken.x);
    }

    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());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                int input = Integer.parseInt(st.nextToken());
                if (input == HOME) {
                    homeList.add(new Pair(i, j));
                }
                else if (input == CHICKEN) {
                    chickenList.add(new Pair(i, j));
                }
            }
        }

        selected = new boolean[chickenList.size()];
        backtrack(0, 0);        // Init Call

        System.out.println(minSumDist);
    }
}

https://www.acmicpc.net/problem/19236

1. 아이디어

• 구현, 시뮬레이션
• 백트래킹, 완전 탐색
  • 각 분기에서 상어의 방향 일직선 상으로 이동 가능한 칸 개수 = 최대 3개

2. 자료구조

• int[][] map

• Fish[] fishes: 1 ~ 16번 물고기 정보

  ※ Fish: 물고기 위치 (y, x), 번호 idx, 방향 dir, 먹힘 여부 alive

3. 시간 복잡도

• 각 분기에서 상어가 이동할 위치 선택: 최대 3개 경우의 수

• 최대 확인해야 하는 경우의 수 = 3^15 = 14,348,907 << 1억 => 완전 탐색 가능

코드

import java.io.*;
import java.util.*;

class Fish {
    public int y, x;            // 물고기 위치
    public int idx, dir;        // 물고기 번호: 1 ~ 16, 방향: 1 ~ 8
    public boolean alive;        // 물고기가 먹혔는지 여부

    public Fish(int y, int x, int idx, int dir, boolean alive) {
        this.y = y;
        this.x = x;
        this.idx = idx;
        this.dir = dir;
        this.alive = alive;
    }
}

public class Main {
    static int[][] map;
    static Fish[] fishes;
    static int maxEatSum;                // 출력

    // 반시계 방향 순서, index [1] ~ [8] 사용: { 제자리, ↑, ↖, ←, ↙, ↓, ↘, →, ↗ }
    static int[] dy = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
    static int[] dx = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
    static final int EMPTY = 0, SHARK = -1;

    static void backtrack(int sharkY, int sharkX, int shakrDir, int eatSum) {
        int[][] tempMap = new int[4][4];        // Copy - map을 되돌려놓기 위해 백업
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                tempMap[i][j] = map[i][j];
            }
        }

        Fish[] tempFishes = new Fish[17];        // Copy - fishes를 되돌려놓기 위해 백업
        for (int i = 1; i <= 16; i++) {
            Fish fish = fishes[i];
            tempFishes[i] = new Fish(fish.y, fish.x, fish.idx, fish.dir, fish.alive);
        }

        // 물고기 번호 순으로 차례로 이동
        moveAllFishes();

        // 상어의 방향 일직선 상에서, 물고기 칸을 선택
        for (int i = 1; i <= 3; i++) {                // 최대 3개 경우의 수
            int ny = sharkY + (dy[shakrDir] * i);
            int nx = sharkX + (dx[shakrDir] * i);

            if (!isValid(ny, nx))
                continue;

            if (1 <= map[ny][nx] && map[ny][nx] <= 16) {    // 이동 선택할 다음 칸이 물고기 칸인 경우
                int fishIdx = map[ny][nx];                    // 잡아먹힐 물고기 번호
                int nDir = fishes[fishIdx].dir;                // 상어의 다음 방향 = 먹은 물고기의 방향

                // 상어가 물고기 칸으로 이동해서 물고기 먹음
                map[sharkY][sharkX] = EMPTY;        // 기존에 상어가 있던 칸
                map[ny][nx] = SHARK;
                fishes[fishIdx].alive = false;
                maxEatSum = Math.max(maxEatSum, eatSum + fishIdx);

                backtrack(ny, nx, nDir,eatSum + fishIdx);

                // backtrack
                map[ny][nx] = fishIdx;
                map[sharkY][sharkX] = SHARK;
                fishes[fishIdx].alive = true;
            }
        }

        map = tempMap;
        fishes = tempFishes;
    }

    static void moveAllFishes() {
        for (int i = 1; i <= 16; i++) {
            // 아직 상어에게 잡아먹히지 않은 남은 물고기인 경우
            if (fishes[i].alive) {
                moveFish(i);
            }
        }
    }

    static void moveFish(int fishIdx) {
        int y = fishes[fishIdx].y;
        int x = fishes[fishIdx].x;
        int dir = fishes[fishIdx].dir;

        // 현재 방향부터 반시계 방향으로
        for (int i = 0; i <= 8; i++) {
            int nDir = (dir + i) % 9;            // i = 0이면, nDir = 현재 방향 dir과 동일
            if (nDir == 0)                        // 본인 제자리 칸은 제외
                continue;

            fishes[fishIdx].dir = nDir;            // 물고기 방향 회전 반영

            int ny = y + dy[nDir];
            int nx = x + dx[nDir];

            if (!isValid(ny, nx))
                continue;

            if (map[ny][nx] == EMPTY) {            // 인접 칸이 빈 칸인 경우
                map[y][x] = EMPTY;                // 기존 칸

                map[ny][nx] = fishIdx;            // 새로 이동하는 칸
                fishes[fishIdx].y = ny;
                fishes[fishIdx].x = nx;

                break;
            }
            else if (1 <= map[ny][nx] && map[ny][nx] <= 16) {    // 인접 칸이 물고기 칸인 경우
                // 물고기 칸끼리 서로 위치 swap
                int nFishIdx = map[ny][nx];

                map[ny][nx] = fishIdx;
                fishes[fishIdx].y = ny;
                fishes[fishIdx].x = nx;

                map[y][x] = nFishIdx;
                fishes[nFishIdx].y = y;
                fishes[nFishIdx].x = x;

                break;
            }
        }
    }

    static boolean isValid(int y, int x) {
        return (0 <= y && y < 4) && (0 <= x && x < 4);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer st;

        map = new int[4][4];
        fishes = new Fish[17];            // [1] ~ [16] 사용
        for (int i = 0; i < 4; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < 4; j++) {
                int idx = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken());

                map[i][j] = idx;
                fishes[idx] = new Fish(i, j, idx, dir, true);
            }
        }

        // 최초: 상어가 [0][0] 위치의 물고기를 먹고, 먹은 물고기 방향을 가짐
        int fishIdx = map[0][0];
        int sharkDir = fishes[fishIdx].dir;        // 상어 방향 = 먹은 물고기 방향

        map[0][0] = SHARK;
        fishes[fishIdx].alive = false;
        fishes[fishIdx].y = -1;
        fishes[fishIdx].x = -1;
        fishes[fishIdx].dir = -1;
        maxEatSum += fishIdx;

        backtrack(0, 0, sharkDir, maxEatSum);        // Init Call

        System.out.println(maxEatSum);
    }
}

https://www.acmicpc.net/problem/16236

1. 아이디어

• 구현, 시뮬레이션
• BFS
  • 먹을 수 있는 물고기 위치 탐색
• PriorityQueue / 정렬
  • BFS 탐색하면서, 먹을 수 있는 물고기 찾으면 PQ에 저장

1) 먹을 수 있는 물고기 탐색

• 현재 아기 상어 위치로부터 BFS 탐색 시작

  • map[][]의 모든 지점을 탐색 (BFS 안에서 while문 종료 조건 명시 X)

• 다음 인접 지점에 대해

  ① 다음 지점을 아직 방문 안했고, 아기 상어가 지나갈 수 있는 칸인 경우

  • BFS 탐색 확장

  ② 다음 지점이 물고기 칸이고, 아기 상어가 먹을 수 있는 경우

  • 해당 물고기 칸을 pq에 저장

2) 물고기 먹기

① pq.isEmpty()인 경우 (먹을 수 있는 물고기가 맵에 없는 경우)

• 반복 종료 및 출력

② pq.isEmpty()가 아닌 경우 (먹을 수 있는 물고기가 1마리 or 다수인 경우)

• pq에서 꺼낸 Node의 먹을 물고기 위치로 아기 상어 이동 및 물고기 먹기, 먹은 물고기 개수 증가 및 아기 상어 크기 증가 확인

먹을 수 있는 물고기 개수가 다수일 경우, 먹으러 갈 물고기 우선순위 정하기 (정렬 기준) ① 거리 작은 순 ② 해당 물고기 행 번호 작은 순 ③ 해당 물고기 열 번호 작은 순

2. 자료구조

• boolean[][] visited

• Queue<Node>, LinkedList<Node>: BFS 수행

• PriorityQueue<Node>: 먹을 물고기 우선순위 지정

  ※ Node: 먹을 물고기 위치 (y, x), 지나온 칸 개수 distance

코드

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
    public int y, x;            // 먹을 물고기 위치
    public int distance;        // 지나온 칸 개수

    public Node(int y, int x, int distance) {
        this.y = y;
        this.x = x;
        this.distance = distance;
    }

    // 거리 작은 순 -> 행 번호 작은 순 -> 열 번호 작은 순
    public int compareTo(Node o) {
        if (this.distance != o.distance)
            return this.distance - o.distance;
        if (this.y != o.y)
            return this.y - o.y;
        return this.x - o.x;
    }
}

public class Main {
    static int n;                    // n x n 행렬
    static int[][] map;
    static int time;                // 출력

    static boolean[][] visited;
    static Queue<Node> queue = new LinkedList<>();                // BFS 탐색
    static PriorityQueue<Node> pq = new PriorityQueue<>();        // 먹을 물고기 저장 및 정렬
    static int sharkY, sharkX;            // 아기 상어 위치
    static int sharkSize = 2;            // 아기 상어 크기 (최초 2)
    static int eatCnt;                    // 아기 상어가 먹은 물고기 개수 (size 증가할 때마다, 0으로 초기화)

    static final int EMPTY = 0;            // 빈 칸
    static final int SHARK = 9;            // 아기 상어 칸
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };

    static void solution() {
        while (true) {
            visited = new boolean[n][n];        // Init
            queue.clear();
            pq.clear();

            // 1) 먹을 수 있는 물고기 count
            // BFS 탐색: 아기 상어 칸 [sharkY][sharkX]에서 나머지 모든 지점 탐색
            visited[sharkY][sharkX] = true;
            queue.add(new Node(sharkY, sharkX, 0));
            bfs();

            // 2) 물고기 먹기
            // 먹을 수 있는 물고기가 맵에 없는 경우
            if (pq.isEmpty()) {
                return;
            }

            // 먹을 수 있는 물고기가 1마리 or 다수인 경우
            Node fish = pq.remove();
            map[sharkY][sharkX] = EMPTY;        // 기존 아기 상어 위치

            map[fish.y][fish.x] = SHARK;
            sharkY = fish.y;
            sharkX = fish.x;

            eatCnt++;
            if (eatCnt == sharkSize) {
                sharkSize++;
                eatCnt = 0;
            }

            time += fish.distance;
        }
    }

    /* 아기 상어 칸 [sharkY][sharkX]에서부터 나머지 모든 지점 탐색 */
    static void bfs() {
        while (!queue.isEmpty()) {
            Node current = queue.remove();

            for (int i = 0; i < 4; i++) {
                int ny = current.y + dy[i];
                int nx = current.x + dx[i];

                if (!isValid(ny, nx))
                    continue;

                // 다음 지점을 아직 방문 안했고, 지나갈 수 있는 칸인 경우
                if (!visited[ny][nx] && sharkSize >= map[ny][nx]) {
                    Node next = new Node(ny, nx, current.distance + 1);
                    visited[ny][nx] = true;
                    queue.add(next);

                    // 아기 상어가 먹을 수 있는 물고기인 경우
                    if (map[ny][nx] != EMPTY && sharkSize > map[ny][nx]) {
                        pq.add(next);
                    }
                }
            }
        }
    }

    static boolean isValid(int y, int x) {
        return (0 <= y && y < n) && (0 <= x && x < n);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == SHARK) {
                    sharkY = i;
                    sharkX = j;
                }
            }
        }

        solution();

        System.out.println(time);
    }
}

https://www.acmicpc.net/problem/20058

1. 아이디어

구현, 시뮬레이션, BFS

1) map을 2^L x 2^L 부분 격자로 나눈 후, 부분 격자 단위로 시계 방향 90도 회전

• 2중 for문으로 map 확인 => i, j = 0 ~ len 반복, 2^L 만큼 증감 rotatePartMap(i, j, 2^L) 호출

※ rotatePartMap(int startY, int startX, int partLen) // partLen = 2^L

2) [i][j]의 인접 위치에 얼음 칸이 3개 미만이면, 해당 위치 얼음 감소

• 2중 for문으로 rotatedMap[i][j]에 인접한 위치의 얼음 칸 개수 count

오답 노트

• 틀린 이유 - 2중 for문 탐색하면서, 얼음 개수를 바로 감소 시켜서 틀림 => boolean[][] checkMelted에 감소시킬 얼음 위치 표시 후, 한꺼번에 처리

3) 가장 큰 덩어리가 차지하는 칸의 개수 maxIceMapCnt 세기

• 2중 for문으로 map 전체 확인
• map[i][j] > 0 (얼음 존재)인 경우, BFS 탐색 시작
• 다음 인접 지점 map[ny][nx]에 대해 아직 방문 안했고, 다음 지점 map[ny][nx]에 얼음이 존재하는 경우 탐색 확장

2. 자료구조

• boolean[][] checkMelted: 얼음 감소시킬 위치 표시 후, 한꺼번에 얼음 감소 처리

• boolean[][] visited

• Queue<Node>, LinkedList<Node>: BFS 수행 => Node: (y, x)

코드

import java.io.*;
import java.util.*;

class Node {
    public int y, x;

    public Node(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static int n;                // 2^n x 2^n 격자 맵
    static int q;                // 파이어스톰 q번 시전
    static int len;                // 격자 맵 세로, 가로 길이 len = 2^n
    static int[][] map;
    static int[][] rotatedMap;
    static int[] lValues;        // 각 시전 단계의 L 값

    static int totalIceCnt;        // 출력1, 전체 얼음 양
    static int maxIceMapCnt;    // 출력2, 최대 얼음 덩어리의 칸 개수

    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static boolean[][] checkMelted;
    static boolean[][] visited;
    static Queue<Node> queue;

    static void solution() {
        for (int l : lValues) {
            int partLen = (int) Math.pow(2, l);        // 부분 격자 크기: 2^L

            // 1) 2^L x 2^L 부분 격자 단위로 90도 회전
            rotatedMap = new int[len][len];            // init
            for (int i = 0; i < len; i += partLen) {
                for (int j = 0; j < len; j += partLen)  {
                    rotatePartMap(i, j, partLen);    // 부분 격자 1개 90도 회전
                }
            }

            // 2) [i][j]의 인접 위치에 얼음 칸이 3개 미만이면, 해당 위치 얼음 감소
            checkMelted = new boolean[len][len];    // 얼음 감소시킬 위치 표시 후, 한꺼번에 처리
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    if (getNearbyIceMapCnt(i, j) < 3 && rotatedMap[i][j] > 0) {
                        checkMelted[i][j] = true;
                    }
                }
            }

            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    if (checkMelted[i][j]) {
                        rotatedMap[i][j]--;
                        totalIceCnt--;
                    }
                }
            }

            // map에 rotatedMap 복사
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    map[i][j] = rotatedMap[i][j];
                }
            }
        }

        queue = new LinkedList<>();
        visited = new boolean[len][len];
        // 3) 가장 큰 덩어리가 차지하는 칸의 개수 maxIceMapCnt 세기
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (!visited[i][j] && map[i][j] > 0) {
                    visited[i][j] = true;
                    queue.add(new Node(i, j));
                    int iceMapCnt = bfs();

                    maxIceMapCnt = Math.max(maxIceMapCnt, iceMapCnt);
                }
            }
        }
    }

     /* partLen = 2^L */
     static void rotatePartMap(int startY, int startX, int partLen) {
         for (int i = 0; i < partLen; i++) {
             for (int j = 0; j < partLen; j++) {
                 rotatedMap[startY + j][startX + partLen - 1 - i] =
                         map[startY + i][startX + j];
             }
         }
     }

     /* (y, x) 위치의 인접한 얼음 칸이 몇 개인지 반환 (0 ~ 4) */
     static int getNearbyIceMapCnt(int y, int x) {
         int cnt = 0;

         for (int i = 0; i < 4; i++) {
             int ny = y + dy[i];
             int nx = x + dx[i];

             if (!isValid(ny, nx))
                 continue;

             if (rotatedMap[ny][nx] > 0)
                 cnt++;
         }

         return cnt;
     }

     static int bfs() {
         int iceMapCnt = 1;

         while (!queue.isEmpty()) {
             Node current = queue.remove();

             for (int i = 0; i < 4; i++) {
                 int ny = current.y + dy[i];
                 int nx = current.x + dx[i];

                 if (!isValid(ny, nx))
                     continue;

                 //    다음 지점을 아직 방문 안했고, 다음 지점이 얼음 칸인 경우
                 if (!visited[ny][nx] && map[ny][nx] > 0) {
                     visited[ny][nx] = true;
                     queue.add(new Node(ny, nx));
                     iceMapCnt++;
                 }
             }
         }

         return iceMapCnt;
     }

     static boolean isValid(int y, int x) {
         return (0 <= y && y < len) && (0 <= x && x < len);
     }

    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());
        q = Integer.parseInt(st.nextToken());
        len = (int) Math.pow(2, n);

        map = new int[len][len];
        for (int i = 0; i < len; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < len; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                totalIceCnt += map[i][j];
            }
        }

        st = new StringTokenizer(br.readLine());
        lValues = new int[q];
        for (int i = 0; i < q; i++) {
            lValues[i] = Integer.parseInt(st.nextToken());
        }

        solution();

        System.out.println(totalIceCnt + "\n" + maxIceMapCnt);
    }
}

https://www.acmicpc.net/problem/14502

1. 아이디어

조합(백트래킹 + 브루트포스), BFS

벽을 반드시 3개 세워서, 바이러스가 최소로 퍼지도록 함

1) 전체 빈 칸에서 벽을 세울 빈 칸 3개 선택

• 세울 벽 위치를 3개 선택 완료한 경우 2), 3) 과정 수행

=> 조합(백트래킹 + 브루트포스)

2) 벽을 세울 3개 빈 칸 선택 후, map에 바이러스 확산 표시

• 각 바이러스 지점에 대해 BFS 수행
  

3) 바이러스 확산 표시된 map에서 안전 영역 칸 count

• 2중 for문

2. 자료구조

• Queue<Point> queue: BFS 수행

• boolean[][] visited

코드

import java.io.*;
import java.util.*;

class Point {
    public int y, x;

    public Point(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static int n, m;                // n x m 행렬
    static int[][] originMap;        // 바이러스 확산 전 맵
    static int[][] virusMap;        // 바이러스 확산 맵
    static int maxCount;            // 출력, 안전 영역 최대 크기

    static Queue<Point> queue = new LinkedList<>();
    static boolean[][] visited;

    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static final int EMPTY = 0, WALL = 1, VIRUS = 2;

    static void backtrack(int wallCnt) {
        // 세울 벽 위치 3개 선택 완료한 경우
        if (wallCnt == 3) {
            visited = new boolean[n][m];        // 초기화
            virusMap = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    virusMap[i][j] = originMap[i][j];
                }
            }

            // 바이러스 확산 표시 => BFS
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (!visited[i][j] && virusMap[i][j] == VIRUS) {
                        visited[i][j] = true;
                        queue.add(new Point(i, j));
                        bfs();
                    }
                }
            }

            // 안전 영역 칸 count
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (virusMap[i][j] == EMPTY) {
                        count++;
                    }
                }
            }
            maxCount = Math.max(maxCount, count);

            return;
        }

        // 세울 벽 위치 선택
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (originMap[i][j] == EMPTY) {
                    originMap[i][j] = WALL;        // 벽 세움
                    backtrack(wallCnt + 1);

                    originMap[i][j] = EMPTY;        // 세운 벽 취소
                }
            }
        }
    }

    static void bfs() {
        while (!queue.isEmpty()) {
            Point current = queue.remove();

            for (int i = 0; i < 4; i++) {
                int ny = current.y + dy[i];
                int nx = current.x + dx[i];

                if (!isValid(ny, nx))
                    continue;

                if (!visited[ny][nx] && virusMap[ny][nx] == EMPTY) {
                    virusMap[ny][nx] = VIRUS;            // 바이러스 확산
                    visited[ny][nx] = true;
                    queue.add(new Point(ny, nx));
                }
            }
        }
    }

    static boolean isValid(int ny, int nx) {
        return (0 <= ny && ny < n) && (0 <= nx && nx < m);
    }

    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());

        originMap = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                originMap[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // Init Call
        backtrack(0);

        System.out.println(maxCount);
    }
}

https://www.acmicpc.net/problem/15683

1. 아이디어

조합(백트래킹 + 브루트포스), 구현, 시뮬레이션

• k개 CCTV의 방향을 모두 정하고, 감시 영역을 표시

• 감시하지 못하는 사각지대 칸 수 count

2. 자료구조

• List<CCTV> inputCCTVList: 입력 CCTV들의 정보

• List<CCTV> cctvList: 조합을 구성한 CCTV들의 정보

• CCTV

  • CCTV 위치 (y, x)
  • CCTV가 바라보는 방향 dir (0 ~ 3, 상우하좌 순서)
  • CCTV 번호 idx (1 ~ 5)

3. 시간 복잡도

O(4^k x n x m) (k: CCTV 개수)

• 1개 CCTV에 대해 바라보는 방향(회전시키는 방법) 4개 => k개 CCTV에 대해, 4^k개 조합

• k개 CCTV의 조합을 구성한 후, CCTV 감시 영역 표시 및 사각지대 칸 수 세기: O(n x m)

코드

import java.io.*;
import java.util.*;

class CCTV {
    public int y, x;        // CCTV 위치
    public int dir;            // CCTV가 바라보는 방향
    public int idx;            // CCTV 번호

    public CCTV(int y, int x, int dir, int idx) {
        this.y = y;
        this.x = x;
        this.dir = dir;
        this.idx = idx;
    }
}

public class Main {
    static int n, m;            // n x m 행렬
    static int[][] inputMap;    // 입력 맵
    static int[][] map;
    static int minCount;        // 출력, 최소 사각지대 칸 수

    static int numOfCCTV;        // CCTV 개수
    static List<CCTV> inputCCTVList = new ArrayList<>();    // 입력 CCTV의 위치, 번호 저장
    static List<CCTV> cctvList = new ArrayList<>();

    static final int EMPTY = 0;
    static final int WALL = 6;
    static final int CHECK = 100;

    static void backtrack(int depth) {
        // 전체 CCTV의 감시 방향을 정한 경우
        if (depth >= numOfCCTV) {
            // map 초기화
            map = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    map[i][j] = inputMap[i][j];
                }
            }

            // map에 CCTV 감시 방향 표시
            for (CCTV cctv : cctvList) {
                checkMonitoringArea(cctv);
            }

            // 사각지대(빈 칸 0) 칸 수 count
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == EMPTY) {
                        count++;
                    }
                }
            }
            minCount = Math.min(minCount, count);

            return;
        }

        // 4개 회전 방향 (dir: 0 ~ 3)
        CCTV cctv = inputCCTVList.get(depth);
        for (int dir = 0; dir < 4; dir++) {
            cctvList.add(new CCTV(cctv.y, cctv.x, dir, cctv.idx));    // dir 0: 상
            backtrack(depth + 1);
            cctvList.remove(depth);
        }
    }

    /* map에 CCTV 감시 영역 표시 */
    static void checkMonitoringArea(CCTV cctv) {
        if (cctv.idx == 1) {
            checkMonitoringAreaCCTV1(cctv);
        }
        else if (cctv.idx == 2) {
            checkMonitoringAreaCCTV2(cctv);
        }
        else if (cctv.idx == 3) {
            checkMonitoringAreaCCTV3(cctv);
        }
        else if (cctv.idx == 4) {
            checkMonitoringAreaCCTV4(cctv);
        }
        else {        // cctv.idx == 5
            checkMonitoringAreaCCTV5(cctv);
        }
    }

    /* 1번 CCTV의 감시 영역 표시 */
    static void checkMonitoringAreaCCTV1(CCTV cctv) {
        if (cctv.dir == 0) {        // 1번 CCTV가 위를 바라보는 경우
            checkUpward(cctv.y, cctv.x);
        }
        else if (cctv.dir == 1) {        // 1번 CCTV가 오른쪽을 바라보는 경우
            checkRightward(cctv.y, cctv.x);
        }
        else if (cctv.dir == 2) {        // 1번 CCTV가 아래를 바라보는 경우
            checkDownward(cctv.y, cctv.x);
        }
        else {        // 1번 CCTV가 왼쪽을 바라보는 경우
            checkLeftward(cctv.y, cctv.x);
        }
    }

    /* 2번 CCTV의 감시 영역 표시 */
    static void checkMonitoringAreaCCTV2(CCTV cctv) {
        if (cctv.dir == 0 || cctv.dir == 2) {        // 2번 CCTV가 위 or 아래를 바라보는 경우
            // 양 옆 일직선으로 감시
            checkRightward(cctv.y, cctv.x);
            checkLeftward(cctv.y, cctv.x);
        }
        else {        // 2번 CCTV가 오른쪽 or 왼쪽을 바라보는 경우
            // 위 아래 일직선으로 감시
            checkUpward(cctv.y, cctv.x);
            checkDownward(cctv.y, cctv.x);
        }
    }

    /* 3번 CCTV의 감시 영역 표시 */
    static void checkMonitoringAreaCCTV3(CCTV cctv) {
        if (cctv.dir == 0) {        // 3번 CCTV가 위를 바라보는 경우
            checkUpward(cctv.y, cctv.x);
            checkRightward(cctv.y, cctv.x);
        }
        else if (cctv.dir == 1) {        // 3번 CCTV가 오른쪽을 바라보는 경우
            checkRightward(cctv.y, cctv.x);
            checkDownward(cctv.y, cctv.x);
        }
        else if (cctv.dir == 2) {        // 3번 CCTV가 아래를 바라보는 경우
            checkDownward(cctv.y, cctv.x);
            checkLeftward(cctv.y, cctv.x);
        }
        else {        // 3번 CCTV가 왼쪽을 바라보는 경우
            checkLeftward(cctv.y, cctv.x);
            checkUpward(cctv.y, cctv.x);
        }
    }

    /* 4번 CCTV의 감시 영역 표시 */
    static void checkMonitoringAreaCCTV4(CCTV cctv) {
        if (cctv.dir == 0) {        // 4번 CCTV가 위를 바라보는 경우
            checkUpward(cctv.y, cctv.x);
            checkLeftward(cctv.y, cctv.x);
            checkRightward(cctv.y, cctv.x);
        }
        else if (cctv.dir == 1) {        // 4번 CCTV가 오른쪽을 바라보는 경우
            checkRightward(cctv.y, cctv.x);
            checkUpward(cctv.y, cctv.x);
            checkDownward(cctv.y, cctv.x);
        }
        else if (cctv.dir == 2) {        // 4번 CCTV가 아래를 바라보는 경우
            checkDownward(cctv.y, cctv.x);
            checkLeftward(cctv.y, cctv.x);
            checkRightward(cctv.y, cctv.x);
        }
        else {        // 4번 CCTV가 왼쪽을 바라보는 경우
            checkLeftward(cctv.y, cctv.x);
            checkUpward(cctv.y, cctv.x);
            checkDownward(cctv.y, cctv.x);
        }
    }

    /* 5번 CCTV의 감시 영역 표시 */
    static void checkMonitoringAreaCCTV5(CCTV cctv) {
        // 5번 CCTV: 상하좌우 4방향 일직선 모두 감시
        // => 바라보는 방향 dir에 상관없이 감시 처리
        checkUpward(cctv.y, cctv.x);
        checkDownward(cctv.y, cctv.x);
        checkRightward(cctv.y, cctv.x);
        checkLeftward(cctv.y, cctv.x);
    }

    // 윗 방향 일직선 감시 표시
    static void checkUpward(int y, int x) {
        for (int ny = y - 1; ny >= 0; ny--) {
            if (!isValid(ny, x) || map[ny][x] == WALL)    // 벽은 통과 불가능
                break;

            if (1 <= map[ny][x] && map[ny][x] <= 5)        // CCTV는 통과
                continue;

            map[ny][x] = CHECK;
        }
    }

    // 아래 방향 일직선 감시 표시
    static void checkDownward(int y, int x) {
        for (int ny = y + 1; ny < n; ny++) {
            if (!isValid(ny, x) || map[ny][x] == WALL)    // 벽은 통과 불가능
                break;

            if (1 <= map[ny][x] && map[ny][x] <= 5)        // CCTV는 통과
                continue;

            map[ny][x] = CHECK;
        }
    }

    // 오른쪽 방향 일직선 감시 표시
    static void checkRightward(int y, int x) {
        for (int nx = x + 1; nx < m; nx++) {
            if (!isValid(y, nx) || map[y][nx] == WALL)    // 벽은 통과 불가능
                break;

            if (1 <= map[y][nx] && map[y][nx] <= 5)        // CCTV는 통과
                continue;

            map[y][nx] = CHECK;
        }
    }

    // 왼쪽 방향 일직선 감시 표시
    static void checkLeftward(int y, int x) {
        for (int nx = x - 1; nx >= 0; nx--) {
            if (!isValid(y, nx) || map[y][nx] == WALL)    // 벽은 통과 불가능
                break;

            if (1 <= map[y][nx] && map[y][nx] <= 5)        // CCTV는 통과
                continue;

            map[y][nx] = CHECK;
        }
    }

    static boolean isValid(int ny, int nx) {
        return (0 <= ny && ny < n) && (0 <= nx && nx < m);
    }

    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());
        minCount = n * m;

        inputMap = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                inputMap[i][j] = Integer.parseInt(st.nextToken());
                if (1 <= inputMap[i][j] && inputMap[i][j] <= 5) {
                    numOfCCTV++;
                    inputCCTVList.add(new CCTV(i, j, -1, inputMap[i][j]));
                }
            }
        }

        // Init Call
        backtrack(0);

        System.out.println(minCount);
    }
}

https://www.acmicpc.net/problem/14503

1. 아이디어

구현, 시뮬레이션

1) 현재 위치 청소

• map[i][j] = CLEAR;
• resultClearCnt++;

2) 현재 위치, 현재 방향을 기준으로 왼쪽 방향부터 차례로 탐색

① 왼쪽 칸을 아직 청소 안한 경우 (청소 안한 빈 칸 EMPTY인 경우)

• 왼쪽 방향으로 회전한 후 1칸 전진하고 1) 부터 다시 진행

② 왼쪽 칸이 이미 청소(CLEAR)되거나 벽(WALL)인 경우

• 왼쪽 방향으로 회전한 후 2) 부터 다시 진행

③ 4방향 모두 청소되거나 벽인 경우

• 현재 방향을 유지한 채로 1칸 후진 후 2) 부터 다시 진행

④ 4방향 모두 청소되거나 벽이고 뒤쪽 방향이 벽인 경우

• 작동 종료

메소드 구현 사항

• int getLeftState(): 현재 위치 (y, x), 방향 d 기준으로 왼쪽 칸의 상태 반환
  • 반환값 = EMPTY / WALL / CLEAR
• void rotateLeft(): 현재 위치 (y, x), 방향 d 기준으로 왼쪽 방향으로 회전
• void moveForward(): 현재 위치 (y, x), 방향 d 기준으로 1칸 전진
• void moveBackward(): 현재 위치 (y, x), 방향 d 기준으로 1칸 후진
• boolean isFourDirectionClearedOrWall(): 현재 위치 (y, x) 기준으로 4방향 모두 청소되거나 벽인지 확인
• boolean existBackWall(): 현재 위치 (y, x), 방향 d 기준으로 뒷 칸이 벽인지 확인

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int n, m;                // n x m 행렬
    static int y, x, d;                // 로봇 청소기의 현재 위치 (y, x), 방향 d
    static int[][] map;
    static int resultClearCnt;        // 출력, 청소하는 영역 칸 개수

    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };

    static final int EMPTY = 0;        // 빈 칸
    static final int WALL = 1;        // 벽
    static final int CLEAR = 2;        // 청소된 칸

    // 로봇 청소기 방향: 북(상0), 동(우1), 남(하2), 서(좌3)
    static final int DIR_UP = 0;
    static final int DIR_RIGHT = 1;
    static final int DIR_DOWN = 2;
    static final int DIR_LEFT = 3;

    static void solution() {
        // 시작 지점 청소
        map[y][x] = CLEAR;
        resultClearCnt++;

        while (true) {
            // 현재 위치, 방향을 기준으로 왼쪽 칸의 상태 확인
            int leftState = getLeftState();

            if (isFourDirectionClearedOrWall()) {
                // ④ 4방향 모두 청소되거나 벽이고 뒤쪽 방향이 벽인 경우, 작동 종료
                if (existBackWall())
                    break;

                // ③ 4방향 모두 청소되거나 벽인 경우(+ 로봇 청소기의 뒷 칸은 벽이 아님)
                moveBackward();
//                continue;
            }
            else if (leftState == EMPTY) {    // ① 왼쪽 칸을 아직 청소 안한 경우
                rotateLeft();
                moveForward();
                map[y][x] = CLEAR;
                resultClearCnt++;
            }
            else if (leftState == CLEAR || leftState == WALL) {        // ② 왼쪽 칸이 이미 청소되거나 벽인 경우
                rotateLeft();
//                continue;
            }
        }
    }

    /** 현재 위치 (y, x) 기준으로 4방향 모두 청소되거나 벽인지 확인
     * - 4방향 중, 청소가 안된 빈 칸(EMPTY)이 존재하면, false 반환 */
    static boolean isFourDirectionClearedOrWall() {
        boolean existEmpty = false;

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (isValid(ny, nx) && map[ny][nx] == EMPTY) {
                existEmpty = true;
                break;
            }
        }

        return !existEmpty;
    }

    /** 현재 위치 (y, x), 방향 d 기준으로 뒷 칸이 벽인지 확인 */
    static boolean existBackWall() {
        if (d == DIR_UP)
            return map[y + 1][x] == WALL;
        else if (d == DIR_RIGHT)
            return map[y][x - 1] == WALL;
        else if (d == DIR_DOWN)
            return map[y - 1][x] == WALL;
        else    // d == DIR__LEFT 인 경우
            return map[y][x + 1] == WALL;
    }

    /** 현재 위치 (y, x), 방향 d 기준으로 1킨 후진 */
    static void moveBackward() {
        if (d == DIR_UP)
            y++;
        else if (d == DIR_RIGHT)
            x--;
        else if (d == DIR_DOWN)
            y--;
        else     // d == DIR__LEFT 인 경우
            x++;
    }

    /** 현재 위치 (y, x), 방향 d 기준으로 1칸 전진 */
    static void moveForward() {
        if (d == DIR_UP)
            y--;
        else if (d == DIR_RIGHT)
            x++;
        else if (d == DIR_DOWN)
            y++;
        else     // d == DIR__LEFT 인 경우
            x--;
    }

    /** 현재 위치 (y, x), 방향 d 기준으로 왼쪽 칸의 상태 반환 (EMPTY / WALL / CLEAR) */
    static int getLeftState() {
        if (d == DIR_UP)
            return map[y][x - 1];
        else if (d == DIR_RIGHT)
            return map[y - 1][x];
        else if (d == DIR_DOWN)
            return map[y][x + 1];
        else    // d == DIR__LEFT 인 경우
            return map[y + 1][x];
    }

    /** 현재 위치 (y, x), 방향 d 기준으로 왼쪽 방향으로 회전 */
    static void rotateLeft() {
        if (d == DIR_UP)
            d= DIR_LEFT;
        else if (d == DIR_RIGHT)
            d = DIR_UP;
        else if (d == DIR_DOWN)
            d = DIR_RIGHT;
        else    // d == DIR__LEFT 인 경우
            d = DIR_DOWN;
    }

    static boolean isValid(int ny, int nx) {
        return (0 <= ny && ny < n) && (0 <= nx && nx < m);
    }

    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());

        st = new StringTokenizer(br.readLine());
        y = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution();

        System.out.println(resultClearCnt);
    }
}

https://www.acmicpc.net/problem/20057

1. 아이디어

구현, 시뮬레이션

• 토네이도 시작 위치: 격자 중앙 칸

  • (n / 2, n / 2)

• 토네이도 이동 규칙

  • 이동 방향: 좌하우상 순서로 반복

  • 이동 칸 수: 좌하우상 한 싸이클 기준, { 1칸, 1칸, 2칸, 2칸 }, { 3칸, 3칸, 4칸, 4칸 }, { 5칸, 5칸, 6칸, 6칸 }, ... => 4방향 한 싸이클 돌고, 2칸씩 늘어남

반복 조건: 토네이도가 맵을 벗어날 때까지 반복

1) 토네이도 이동

• 토네이도 다음 위치 (nTornadoY, nTornadoX) 계산

  • 토네이도 다음 위치가 맵을 벗어난 경우 (이동했을 때 맵을 벗어난 경우), 반복 종료 및 출력

• 토네이도 다음 위치의 모래 흩날리기

  int nextPosSand = map[nTornadoY][nTornadoX];    // temp 저장 (흩날려서 확산된 모래 양을 빼준 값 계산 용도)
  map[nTornadoY][nTornadoX] = 0;

2) 모래 흩날리기

• 각 지점마다 해당 비율에 따른 모래를 더해줌. 해당 지점에 더해준 흩날린 모래 양을 sumSpreadSand에 더해줌.

  • 흩날리는 모래가 더해지는 지점이 맵을 벗어난 경우, 흩날리는 모래 양을 출력 변수에 더해줌

• 각 지점 비율에 따라 모래를 더해주고, 남은 모래를 알파 지점에 더해줌 알파 지점에 더해줄 남은 모래 양 = nextPosSand - sumSpreadSand

  • 알파 지점이 맵을 벗어난 경우, 알파 지점에 더해지는 모래 양을 출력 변수에 더해줌

• 현재 토네이도 위치 갱신 (다음 위치로 이동 반영)

• 이동 칸 수 배열 dd[]의 각 원소 값 += 2

2. 자료구조

1) 토네이도 이동 방향 4개: 좌하우상 순서

• int[] dy = { 0, 1, 0, -1 }

• int[] dx = { -1, 0, 1, 0 }

• 토네이도 이동 한 싸이클: 좌하우상

  토네이도 다음 위치 y 좌표: nTornadoY = y + dy[i]

2) 토네이도 이동 방향에 따른, 이동 칸 수

• int[] dd = { 1, 1, 2, 2 } => 토네이도 이동 한 싸이클을 돌고난 후, dd[] 각 원소 += 2
  

3) 모래 흩날리는 비율: 9개 지점에 대한 비율

• double[] spreadRatio = { 0.01, 0.01, 0.07, 0.02, 0.07, 0.02, 0.1, 0.1, 0.05 }
  

4) 토네이도 이동 방향에 따른, 모래 확산 방향 (그림 예시 y 지점 기준)

• int[][] dsy = {
        { 토네이도가 왼쪽으로 이동할 때, 모래 확산 y 방향 9개 },
        { 토네이도가 아래쪽으로 이동할 때, 모래 확산 y 방향 9개 },
        { 토네이도가 오른쪽으로 이동할 때, 모래 확산 y 방향 9개 },
        { 토네이도가 위쪽으로 이동할 때, 모래 확산 y 방향 9개 }
  }

• int[][] dsx = {
         { 토네이도가 왼쪽으로 이동할 때, 모래 확산 x 방향 9개 },
        { 토네이도가 아래쪽으로 이동할 때, 모래 확산 x 방향 9개 },
        { 토네이도가 오른쪽으로 이동할 때, 모래 확산 x 방향 9개 },
        { 토네이도가 위쪽으로 이동할 때, 모래 확산 x 방향 9개 }
  }

• dsy[토네이도 이동 방향: 0 ~ 3][0 ~ 8]

  토네이도 다음 위치 y 좌표 nTornadoY에 대해, 흩날려서 확산되는 모래 지점 y 좌표: nTornadoY + dsy[토네이도 이동 방향][0 ~ 8]

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n;                // n x n 행렬
    static int[][] map;            // 각 칸의 모래 양
    static int sumOutSand;        // 출력, 맵 밖으로 나가는 모래 양
    static int tornadoY, tornadoX;            // 현재 토네이도의 위치

    // 토네이도 이동 방향: 좌하우상
    static int[] dy = { 0, 1, 0, -1 };
    static int[] dx = { -1, 0, 1, 0 };

    // 토네이도 이동 방향에 따른, 이동 칸 수 (좌하우상 1 싸이클 돌고, 각각 2칸 씩 커짐)
    static int[] dd = { 1, 1, 2, 2 };        // { 1, 1, 2, 2 } => { 3, 3, 4, 4 } => { 5, 5, 6, 6 } => ...

    // 토네이도가 날리는 모래 비율
    static double[] spreadRatio = { 0.01, 0.01, 0.07, 0.02, 0.07, 0.02, 0.1, 0.1, 0.05 };

    // 토네이도 이동 방향에 따른, 모래 확산 방향 (예시 y 지점 기준)
    static int[][] dsy = {        // 좌하우상 순서
            { -1, 1, -1, -2, 1, 2, -1, 1, 0 },        // 1%, 1%, 7%, 2%, 7%, 2%, 10%, 10%, 5%
            { -1, -1, 0, 0, 0, 0, 1, 1, 2 },
            { 1, -1, 1, 2, -1, -2, 1, -1, 0 },
            { 1, 1, 0, 0, 0, 0, -1, -1, -2 }
    };
    static int[][] dsx = {        // 좌하우상 순서
            { 1, 1, 0, 0, 0, 0, -1, -1, -2 },
            { -1, 1, -1, -2, 1, 2, -1, 1, 0 },
            { -1, -1, 0, 0, 0, 0, 1, 1, 2 },
            { 1, -1, 1, 2, -1, -2, 1, -1, 0 }
    };

    static void solution() {
        while (true) {
            // 좌하우상 한 싸이클
            for (int moveDir = 0; moveDir < 4; moveDir++) {        // 4개 토네이도 이동 방향
                for (int moveCnt = 0; moveCnt < dd[moveDir]; moveCnt++) {        // 각 방향, 규칙에 따라 이동 칸 수
                    // 1) 토네이도 이동
                    int nTornadoY = tornadoY + dy[moveDir];
                    int nTornadoX = tornadoX + dx[moveDir];

                    // 토네이도 다음 이동 위치가 맵을 벗어나면([0][0] 왼쪽으로 벗어난 경우), 종료
                    if (!isValid(nTornadoY, nTornadoX)) {
                        return;
                    }

                    // 이동한 위치의 모래 날리기
                    int nextPosSand = map[nTornadoY][nTornadoX];    // temp 저장
                    map[nTornadoY][nTornadoX] = 0;

                    int sumSpreadSand = 0;            // 흩날려서 분배된 모래 양
                    for (int spreadDir = 0; spreadDir < 9; spreadDir++) {    // 9개 모래 확산 방향
                        int spreadY = nTornadoY + dsy[moveDir][spreadDir];
                        int spreadX = nTornadoX + dsx[moveDir][spreadDir];
                        // 모래가 흩날려서 [spreadY][spreadX] 지점에 더해지는 양
                        int spreadAmount = (int) (nextPosSand * spreadRatio[spreadDir]);

                        if (!isValid(spreadY, spreadX)) {        // 흩날리는 모래가 맵을 벗어난 경우
                            sumOutSand += spreadAmount;
                        }
                        else {
                            map[spreadY][spreadX] += spreadAmount;
                        }
                        sumSpreadSand += spreadAmount;
                    }

                    // 알파 지점에 흩날리고 남은 모래 더해주기
                    int alphaY = nTornadoY + dy[moveDir];
                    int alphaX = nTornadoX + dx[moveDir];
                    int alphaSandAmount = nextPosSand - sumSpreadSand;

                    if (!isValid(alphaY, alphaX)) {
                        sumOutSand += alphaSandAmount;
                    }
                    else {
                        map[alphaY][alphaX] += alphaSandAmount;
                    }

                    // 현재 토네이도 위치 갱신 (다음 위치로 이동 반영)
                    tornadoY = nTornadoY;
                    tornadoX = nTornadoX;
                }
            }

            // 이동 칸 수 2칸씩 증가
            for (int i = 0; i < 4; i++) {
                dd[i] += 2;
            }
        }
    }

    static boolean isValid(int ny, int nx) {
        return (0 <= ny && ny < n) && (0 <= nx && nx < n);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 토네이도 시작 위치: 격자 중간 지점
        tornadoY = n / 2;
        tornadoX = n / 2;

        solution();

        System.out.println(sumOutSand);
    }
}

https://www.acmicpc.net/problem/21608

1. 아이디어

구현, 시뮬레이션, 자료구조 (PriorityQueue, HashSet)

1) 빈 칸 중, 좋아하는 학생이 인접 칸에 가장 많은 칸 선택

• map[1][1] ~ map[n][n] 차례로 확인
  • [y][x] 지점의 인접 칸에 존재하는 studentIdx번 학생이 좋아하는 학생 수 카운트
    

2) 1)을 만족하는 칸이 여러 개인 경우, 인접한 빈 칸이 가장 많은 칸 선택

• map[1][1] ~ map[n][n] 차례로 확인
  • int countNearbyEmptySeat(int y, int x): [y][x] 지점의 인접한 빈 칸 수 카운트

3) 2)를 만족하는 칸이 여러 개인 경우, 행 번호 낮은 칸, 열 번호 낮은 칸 선택

2. 자료구조

• int[][] map: 학생 자리 지정 맵

  • map[i][j] = 0 이면, 해당 자리는 빈 칸

  • map[i][j] = k (k != 0) 이면, 해당 자리에 k번 학생 존재

• List<Integer>, ArrayList<Integer> studentOrderList: 학생 자리 지정 순서 (입력 학생 번호 순서)

  • Set<Integer>[] likeStudentSets: 각 학생이 좋아하는 4명의 학생 저장 ex) likeStudentSets[i]: [i]번 학생이 좋아하는 학생들의 번호 저장

  • PriorityQueue<Node>: 학생 자리 지정 기준에 따라 정렬

    • Node: 인접 칸에 존재하는 좋아하는 학생 수, 인접 칸에 존재하는 빈 자리 수, 자리 위치

    • 정렬: 좋아하는 학생 수 많은 순 -> 빈 자리 많은 순 -> 자리 행, 열 번호 작은 순

3. 시간 복잡도

• 학생 1명의 자리 지정: (n^2 x 4) + (n^2 log_2 n^2)

  • n^2 칸의 맵 전체 확인: n^2

  • 각 칸마다 4개 인접 칸 확인

  • 해당 칸의 정보 Node를 PriorityQueue에 추가하여 힙 정렬

  => O(4 x n^2 + 2 x n^2 log_2 n) = O(n^2 + n^2 log_2 n) = O(n^2 log_2 n)

• 전체 학생 n^2명의 자리 지정: n^2 x n^2 log_2 n => O(n^4 x log_2 n)

코드

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
    public int likeStudentCnt;        // 인접 칸에 존재하는 좋아하는 학생 수
    public int emptySeatCnt;        // 인접 칸에 존재하는 빈 자리 수
    public int y, x;                // 해당 자리 위치

    public Node(int likeStudentCnt, int emptySeatCnt, int y, int x) {
        this.likeStudentCnt = likeStudentCnt;
        this.emptySeatCnt = emptySeatCnt;
        this.y = y;
        this.x = x;
    }

    public int compareTo(Node o) {
        // likeStudentCnt 많은 순 -> emptySeatCnt 많은 순 -> y 작은 순 -> x 작은 순
        if (this.likeStudentCnt != o.likeStudentCnt) {
            return o.likeStudentCnt - this.likeStudentCnt;
        }
        if (this.emptySeatCnt != o.emptySeatCnt) {
            return o.emptySeatCnt - this.emptySeatCnt;
        }
        if (this.y != o.y) {
            return this.y - o.y;
        }
        return this.x - o.x;
    }
}

public class Main {
    static int n;                    // n x n 행렬
    static int numOfStudent;        // 전체 n^2명 학생
    static int resultSum;            // 출력, 학생들의 만족도 합

    static int[][] map;                // 학생 자리 지정 맵
    static List<Integer> studentOrderList = new ArrayList<>();    // 학생 자리 지정 순서 (입력 학생 번호 순서)
    static Set<Integer>[] likeStudentSets;                        // 각 학생이 좋아하는 4명의 학생
    static PriorityQueue<Node> pq = new PriorityQueue<>();        // 학생 자리 지정 기준 정렬
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };

    static void solution() {
        // 모든 학생들의 자리 지정
        selectStudentsSeat();

        // 모든 학생의 자리 지정 완료 후, 학생의 만족도 합 계산
        calcStudentsSatisfaction();
    }

    /* 차례로 학생들의 자리 지정 */
    static void selectStudentsSeat() {
        // 입력 학생 번호 순서에 따라, 차례로 자리 지정
        for (int studentIdx : studentOrderList) {
            // studentIdx번 학생이 좋아하는 학생들의 번호
            Set<Integer> likeStudentSet = likeStudentSets[studentIdx];

            for (int y = 1; y <= n; y++) {
                for (int x = 1; x <= n; x++) {
                    if (map[y][x] != 0)            // [y][x] 칸이 빈 자리인 경우만 확인
                        continue;

                    int likeStudentCnt = 0;        // 인접 칸에 존재하는 좋아하는 학생 수
                    int emptySeatCnt = 0;        // 인접 칸에 존재하는 빈 자리 수

                    for (int i = 0; i < 4; i++) {
                        int ny = y + dy[i];        // 인접 칸 (ny, nx)
                        int nx = x + dx[i];

                        if (!isValid(ny, nx))
                            continue;

                        // 인접 칸이 빈 자리인 경우
                        if (map[ny][nx] == 0) {
                            emptySeatCnt++;
                        }
                        // 인접 칸에 좋아하는 학생이 존재하는 경우
                        else if (likeStudentSet.contains(map[ny][nx])) {
                            likeStudentCnt++;
                        }
                    }

                    pq.add(new Node(likeStudentCnt, emptySeatCnt, y, x));
                }
            }

            // 맵의 모든 칸을 확인한 후, studentIdx번 학생의 자리를 규칙에 따라 선택
            Node selected = pq.remove();
            map[selected.y][selected.x] = studentIdx;        // studentIdx번 학생 자리 지정 완료

            pq.clear();            // pq 초기화
        }
    }

    /* 학생의 만족도 합 계산 */
    static void calcStudentsSatisfaction() {
        for (int y = 1; y <= n; y++) {
            for (int x = 1; x <= n; x++) {
                int studentIdx = map[y][x];
                int likeStudentCnt = 0;
                Set<Integer> likeStudentSet = likeStudentSets[studentIdx];

                // studentIdx번 학생의 자리 인접 칸에 앉은 좋아하는 학생 수 카운트
                for (int i = 0; i < 4; i++) {
                    int ny = y + dy[i];
                    int nx = x + dx[i];

                    if (isValid(ny, nx) && likeStudentSet.contains(map[ny][nx])) {
                        likeStudentCnt++;
                    }
                }

                if (likeStudentCnt == 1) resultSum += 1;
                else if (likeStudentCnt == 2) resultSum += 10;
                else if (likeStudentCnt == 3) resultSum += 100;
                else if (likeStudentCnt == 4) resultSum += 1000;
            }
        }
    }

    static boolean isValid(int ny, int nx) {
        return (1 <= ny && ny <= n && 1 <= nx && nx <= n);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        numOfStudent = n * n;

        map = new int[n + 1][n + 1];                    // [1][1] ~ [n][n] 사용
        likeStudentSets = new Set[numOfStudent + 1];    // [1] ~ [numOfStudent] 사용
        for (int i = 1; i <= numOfStudent; i++) {
            likeStudentSets[i] = new HashSet<>();
        }

        for (int i = 0; i < numOfStudent; i++) {
            st = new StringTokenizer(br.readLine());
            int studentIdx = Integer.parseInt(st.nextToken());
            int s1 = Integer.parseInt(st.nextToken());
            int s2 = Integer.parseInt(st.nextToken());
            int s3 = Integer.parseInt(st.nextToken());
            int s4 = Integer.parseInt(st.nextToken());

            studentOrderList.add(studentIdx);

            // studentIdx번 학생이 s1, s2, s3, s4 학생을 좋아함
            likeStudentSets[studentIdx].add(s1);
            likeStudentSets[studentIdx].add(s2);
            likeStudentSets[studentIdx].add(s3);
            likeStudentSets[studentIdx].add(s4);
        }

        solution();

        System.out.println(resultSum);
    }
}

https://www.acmicpc.net/problem/21609

1. 아이디어

BFS, 구현, 시뮬레이션

• 블록 그룹의 기준 블록 = 일반 블록 중, 행 번호가 가장 작은 블록 -> 열 번호가 가장 작은 블록

오토 플레이: 블록 그룹이 존재하는 동안 반복

1) 크기가 가장 큰 블록 그룹 찾기

• 동일 크기 블록 그룹이 여러 개인 경우, 무지개 블록 개수가 많은 블록 그룹 -> 기준 블록의 행 번호가 큰 것 -> 기준 블록의 열 번호가 큰 것

• map[0][0] ~ map[n-1][n-1] 차례로 확인, map[i][j] 지점에서 BFS 탐색 시작 => bfs_findBlockGroup()로 탐색한 BlockGroup을 PriorityQueue<BlockGroup>에 추가
  • PriorityQueue<BlockGroup>에서 remove한 BlockGroup 선택 ※ PriorityQueue.isEmpty()인 경우, 오토플레이 반복 종료 및 출력

2) 1)에서 찾은 블록 그룹의 모든 블록 제거, 제거한 (블록 수)^2 점 획득

• BFS 탐색 수행하며 블록 제거 => bfs_deleteBlockGroup()

• 1)에서 찾은 BlockGroup의 블록 크기 (groupSize)^2 을 출력 변수에 더함

3) 격자에 중력 작용

• 검은색 블록을 제외한 모든 블록(무지개, 일반 블록)이 행 번호가 큰 칸(아래 칸)으로 이동

• 이동: 다른 블록 or 격자 경계를 만나기 전까지 계속됨
  • 격자 맵 1열씩 확인: 아래에서 두 번째 칸부터 윗 칸으로 확인, j = n-2 ~ 0 => map[j][i]에 대해 아랫 칸 map[j-1][i]이 삭제된 칸(DELETED)인 경우, map[j][i]의 블록이 아랫 칸 map[j-1][i]으로 내려감 (map[j-1][i] = map[j][i])

4) 격자 90도 반시계 방향 회전

• int[][] rotatedMap에 회전한 맵 저장 후, 기존 map에 복사

• map[0][0] ~ map[n-1][n-1] 확인 => rotatedMap[n-1-j][i] = map[i][j];

5) 격자에 중력 작용

오답 노트
1) 방문 처리 배열

• 무지개 블록은 블록 그룹 간에 중복 가능하므로, 무지개 블록의 방문 처리를 구분해야 함
• 2중 for문에서 블록 그룹을 찾는 BFS를 호출할 때(BFS 바깥)의 방문 처리와 블록 그룹을 찾는 BFS 내부에서의 방문 처리를 구분해야 함
  
  ① boolean[][] visited1
  • 일반 블록만 방문 처리 (무지개 블록은 방문 처리 X)
  • 블록 그룹 간에 무지개 블록이 중복 가능함을 고려
  • 블록 그룹을 찾는 BFS 바깥에서 해당 지점 방문 여부 확인
  • map[y][x] >= 1 (일반 블록)이고 !visited1[y][x]인 경우, BFS 탐색 시작
  • BFS 탐색 중, 무지개 블록은 방문 처리 X, 일반 블록만 방문 처리
  • 한 블록 그룹에 대해 BFS 탐색이 끝나면, 해당 블록 그룹의 일반 블록만 방문 처리됨
    
    ② boolean[][] visited2
  • 일반 블록 + 무지개 블록 방문 처리
  • 블록 그룹을 찾는 BFS 내부에서 해당 지점 방문 여부 확인
  • BFS 탐색 시작할 때, visited2 초기화
  • map[y][x] >= 0 (무지개 or 일반 블록)이고 !visited2[y][x] 인 경우, BFS 탐색 확장
  • map[y][x] == 0 (무지개 블록) 이면, visited2[y][x] = true; 처리
  • map[y][x] >= 1 (일반 블록) 이면, visited1[y][x] = true; visited2[y][x] = true; 처리
  • BFS 탐색 중, 일반 블록과 무지개 블록 모두 방문 처리
    >
  • 2) 방문 처리 배열, 큐 초기화 시점 순서 처리*
    >
  • 3) 블록 그룹 찾는 BFS 메소드에서 블록 그룹 크기 groupSize 초기화 실수*
• 블록 그룹 찾는 BFS 메소드에 들어온 순간(BFS 탐색을 시작한 순간) = 이미 일반 블록 1개를 찾은 시점
• groupSize = 0; 이 아닌, groupSize = 1;로 초기화 해야함
  > **4) 격자 맵에 중력 작용 메소드**
• while문 내부에서, curRow 사용 안한 실수

2. 자료구조

• boolean[][] visited1: 블록 그룹을 찾는 BFS 바깥에서 일반 블록만 방문 처리

• boolean[][] visited2: 블록 그룹을 찾는 BFS 내부에서 일반 + 무지개 블록 방문 처리

• boolean[][] visited3: 찾은 블록 그룹을 삭제하는 BFS에서 블록 방문 처리

• Queue<Node>, LinkedList<Node>: BFS 수행

  • Node: 현재 위치 (y, x)

• PriorityQueue<BlockGroup>: 블록 그룹의 정보 BlockGroup들을 기준에 따라 정렬하여, 오토플레이할 블록 그룹 선택

  • BlockGroup: 블록 그룹 크기, 무지개 블록 개수, 기준 블록 위치

코드

import java.io.*;
import java.util.*;

class Node {
    public int y, x;            // 현재 탐색 위치

    public Node(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

class BlockGroup implements Comparable<BlockGroup> {
    public int groupSize;                // 블록 그룹 크기 (일반 블록 개수 + 무지개 블록 개수)
    public int rainbowCnt;                // 무지개 블록 개수
    public int standardY, standardX;    // 기준 블록 위치

    public BlockGroup(int groupSize, int rainbowCnt, int standardY, int standardX) {
        this.groupSize = groupSize;
        this.rainbowCnt = rainbowCnt;
        this.standardY = standardY;
        this.standardX = standardX;
    }

    // 블록 그룹 크기(일반 블록 개수 + 무지개 블록 개수)가 큰 순 -> 무지개 블록 개수가 많은 순
    // -> 기준 블록의 행 번호가 큰 순 -> 기준 블록의 열 번호가 큰 순
    public int compareTo(BlockGroup o) {
        if (this.groupSize != o.groupSize) {
            return o.groupSize - this.groupSize;
        }
        if (this.rainbowCnt != o.rainbowCnt) {
            return o.rainbowCnt - this.rainbowCnt;
        }
        if (this.standardY != o.standardY) {
            return o.standardY - this.standardY;
        }
        return o.standardX - this.standardX;
    }
}

public class Main {
    static int n;            // n x n 행렬
    static int m;            // m개 일반 블록 색상 (1 ~ m)
    static int[][] map;
    static int sumPoint;    // 출력, 획득한 점수 합

    static final int RAINBOW = 0;            // 무지개 블록
    static final int DELETED = -999;        // 제거된 블록 표시
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };

    // visited1: 블록 그룹 찾기할 때, BFS 바깥에서 방문 처리 (무지개 블록은 방문 처리 X)
    // visited2: 블록 그룹을 찾는 BFS 안에서 방문 처리 (해당 블록 그룹의 모든 블록(일반, 무지개)에 대해 방문 처리)
    // visited3: 블록 그룹을 삭제하는 BFS에서 방문 처리
    static boolean[][] visited1;
    static boolean[][] visited2;
    static boolean[][] visited3;
    static Queue<Node> queue;
    static PriorityQueue<BlockGroup> pq = new PriorityQueue<>();    // Node 정렬하여, 규칙에 따라 블록 그룹 선택

    static void solution() {
        // 오토 플레이: 블록 그룹이 존재하는 동안 반복
        while (true) {
            // 1) 규칙 우선순위에 따라 삭제할 블록 그룹 찾기
            visited1 = new boolean[n][n];        // 무지개 블록은 방문 처리 X

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // 아직 방문 안했고 일반 블록인 경우, BFS 탐색 시작
                    if (!visited1[i][j] && map[i][j] >= 1) {
                        bfs_findBlockGroup(i, j, map[i][j]);    // PQ에 탐색한 블록 그룹 추가
                    }
                }
            }

            if (pq.isEmpty()) {        // 블록 그룹이 더 이상 없는 경우, 종료 및 출력
                break;
            }

            BlockGroup blockGroup = pq.remove();        // 삭제할 블록 그룹
            pq.clear();

            // 2) 찾은 블록 그룹의 모든 블록 제거, 제거한 (블록 수)^2 점 획득
            bfs_deleteBlockGroup(blockGroup.standardY, blockGroup.standardX);
            sumPoint += (blockGroup.groupSize * blockGroup.groupSize);

            // 3) 격자 맵에 중력 작용
            fallGravity();

            // 4) 격자 맵 90도 반시계 방향 회전
            rotateCounterClock();

            // 5) 격자 맵에 중력 작용
            fallGravity();
        }
    }

    /** 블록 그룹(normalColor 색상의 일반 블록 + 무지개 블록)을 BFS 탐색
     * - (standardY, standardX): 기준 블록 위치, BFS 탐색 시작 위치 */
    static void bfs_findBlockGroup(int standardY, int standardX, int normalColor) {
        int groupSize = 1;        // 블록 그룹 크기 (일반 블록 개수 + 무지개 블록 개수)
        int rainbowCnt = 0;        // 무지개 블록 개수

        visited2 = new boolean[n][n];
        queue = new LinkedList<>();

        visited1[standardY][standardX] = true;
        visited2[standardY][standardX] = true;
        queue.add(new Node(standardY, standardX));

        while (!queue.isEmpty()) {
            Node current = queue.remove();

            for (int i = 0; i < 4; i++) {
                int ny = current.y + dy[i];
                int nx = current.x + dx[i];

                if (!isValid(ny, nx) || visited2[ny][nx])
                    continue;

                // 색상이 같은 일반 블록 or 무지개 블록인 경우, 탐색 확장 (블록 그룹에 포함)
                if (map[ny][nx] == normalColor) {
                    groupSize++;
                    visited1[ny][nx] = true;
                    visited2[ny][nx] = true;
                    queue.add(new Node(ny, nx));
                }
                else if (map[ny][nx] == RAINBOW) {
                    groupSize++;
                    rainbowCnt++;
                    // visited1: 무지개 블록은 방문 처리 X => 블록 그룹 간에 무지개 블록 중복 가능
                    visited2[ny][nx] = true;
                    queue.add(new Node(ny, nx));
                }
            }
        }

        if (groupSize >= 2) {        // 블록 그룹은 2개 이상의 블록으로 구성되어야 함
            pq.add(new BlockGroup(groupSize, rainbowCnt, standardY, standardX));
        }
    }

    /** 블록 그룹의 블록들을 BFS로 탐색하며 삭제 */
    static void bfs_deleteBlockGroup(int y, int x) {
        visited3 = new boolean[n][n];
        queue = new LinkedList<>();

        // blockGroup의 일반 블록 색상
        int normalColor = map[y][x];

        // blockGroup의 기준 블록 위치 (standardY, standardX)에서 BFS 탐색 시작
        map[y][x] = DELETED;        // 블록 삭제
        visited3[y][x] = true;
        queue.add(new Node(y, x));

        while (!queue.isEmpty()) {
            Node current = queue.remove();

            for (int i = 0; i < 4; i++) {
                int ny = current.y + dy[i];
                int nx = current.x + dx[i];

                if (!isValid(ny, nx))
                    continue;

                if (visited3[ny][nx])
                    continue;

                if (map[ny][nx] == normalColor || map[ny][nx] == RAINBOW) {
                    map[ny][nx] = DELETED;            // 블록 삭제
                    visited3[ny][nx] = true;
                    queue.add(new Node(ny, nx));
                }
            }
        }
    }

    /** 격자 맵에 중력 작용
     * - 검은색 블록을 제외한 모든 블록(무지개, 일반 블록)이 행 번호가 큰 칸(아래 칸)으로 이동*/
    static void fallGravity() {
        // 격자 맵 1열씩 확인: [0]열 ~ [n-1]열 확인
        for (int col = 0; col < n; col++) {
            // 아래에서 두 번째 칸부터 윗 칸으로 확인: [n-2]행 ~ [0]행
            for (int row = n - 2; row >= 0; row--) {
                if (map[row][col] >= RAINBOW) {                // 무지개 or 일반 블록인 경우, 중력 작용
                    if (map[row + 1][col] == DELETED) {        // 블록 아래 칸이 삭제된 칸인 경우
                        int curRow = row;        // 중력 작용하는 블록(일반 or 무지개)의 행
                        int nRow = row + 1;        // 중력 작용하는 블록 아랫 칸에 있는 삭제된 칸의 행

                        // 중력이 작용하는 블록의 아래 칸에 다른 블록 or 격자가 나올 때까지 중력 작용 반복
                        while (nRow < n && map[nRow][col] == DELETED) {
                            map[nRow][col] = map[curRow][col];
                            map[curRow][col] = DELETED;

                            curRow++;
                            nRow++;
                        }
                    }
                }
            }
        }
    }

    /** 격자 맵 90도 반시계 방향으로 회전 */
    static void rotateCounterClock() {
        // rotatedMap에 회전한 맵 저장 후, 기존 map에 복사
        int[][] rotatedMap = new int[n][n];
        for (int i = 0 ; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rotatedMap[n - 1 - j][i] = map[i][j];
                // rotatedMap[i][j] = map[j][n - 1 - i];
            }
        }
        map = rotatedMap;
    }

    static boolean isValid(int ny, int nx) {
        return (0 <= ny && ny < n) && (0 <= nx && nx < n);
    }

    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][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solution();

        System.out.println(sumPoint);
    }
}