정범의 프로그래밍 블로그 입니다.

5 분 소요

1. 핵심 개념 및 근거

필요한 개념 및 자료구조

  • 시뮬레이션: 문제에 제시된 시간 흐름에 따라 객체의 상태 변화를 그대로 코드로 옯기는 방식입니다.
  • Queue: 매 시간(M)마다 현재 살아있는 군집들을 관리하고, 다음 상태로 넘기기 위해 사용합니다.
  • 2차원 객체 배열: 이동 후 동일한 좌표에 여러 군집이 모이는 충돌 상황을 O(1)의 접근 속도로 판단하기 위해 사용합니다.
  • 사용자 정의 클래스: 좌표, 미생물 수, 방향, 그리고 방향 결정을 위한 최대 미생물 수 데이터를 묶어서 관리합니다.

선택 근거

  • 시뮬레이션 근거: 문제에서 M시간 동안, 매 시간마다, 동시에 이동이라는 구체적인 행동 지침이 주어졌기 때문입니다.


2. 추론 과정

  • 동시에 이동
    • A가 이동한 자리에 B가 올 수 있습니다.
    • 따라서 이동 전 데이터와 이동 중인 데이터를 분리해야 함을 깨닫고 Queue나 임시 배열을 떠올려야 합니다.
  • 약품이 칠해진 셀
    • 좌표값이 0 또는 N - 1인 경우입니다.
  • 가장 많은 미생물 수의 방향
    • 여러 군집이 합쳐질 때 기준이 필요합니다.
    • 단순히 totalCnt만 더하는게 아니라, 합쳐지기 전 개별 군집 중 최대값을 기억할 변수(maxCnt)가 클래스 내에 필요함을 추론합니다.


3. 설계 및 접근

  1. 초기화: 입력받은 군집 정보를 Cluster 객체로 만들어 Queue에 넣습니다.
  2. 이동: 큐에서 하나씩 꺼내 dr[dir], dc[dir]을 더해 좌표를 갱신합니다.
  3. 약품 처리: 갱신된 좌표가 가장자리라며 cnt/2를 하고 방향을 반대로 꺾습니다.
    1. 이때 cnt가 0이면 소멸합니다.
  4. 충돌/병합: 2차원 객체 배열 map[r][c]를 확인합니다.
    • 비어있으면 현재 군집을 배치합니다.
    • 이미 군집이 있다면, 기존 maxCnt와 현재 군집의 cnt를 비교해 결정하고 전체 cnt를 누적합니다.
  5. 반복: 맵에 남은 객체들을 다시 큐에 담고 이 과정을 M번 반복합니다.


4. 예시 시뮬레이션

상황: N = 4, 1초후 map[1][1]에서 군집 A(10, 우)와 B(20, 좌)가 만나는 경우

  1. A이동: map[1][1]에 도착.map[1][1]이 비어있으므로 등록. (cnt=10, maxCnt=10, dir=우)
  2. B이동: map[1][1]에 도착. map[1][1]에 이미 A가 있음.
    • map[1][1].maxCnt(10) < B.cnt(20)이므로, 이 칸의 방향은 B 방향인 좌로 변경됩니다.
    • 미생물 수는 합쳐져서 map[1][1].cnt = 30이 됩니다.
  3. 결과: 다음 턴에 이 칸의 정보는 (1, 1, 30, 좌)가 됩니다.


5. 주의 사항

  • 어려운 포인트
    • 방향 결정 시점은 해당 턴에 그 칸에 군집들 중 가장 컸던 녀석의의 방향을 써야 합니다.
    • 이미 합쳐진 누적값과 비교하면 안 됩니다.
  • 실수 포인트
    • 방향 인덱스 실수
    • 미생물 수가 1일 때 약품 처리하면 0이 되어 사라져야 하는데 이를 처리하지 않는 경우
    • 매 시간(M)마다 2차원 배열(map)을 새로 생성하거나 초기화하지 않는 경우


6. 코드 풀이

6.1 초기화

Queue<Cluster> q = new LinkedList<>();

for (int i = 0; i < K; i++) {
    st = new StringTokenizer(br.readLine());
    int r = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());
    int cnt = Integer.parseInt(st.nextToken());
    int dir = Integer.parseInt(st.nextToken());
    
    q.add(new Cluster(r, c, cnt, dir, cnt));
}
  • 입력받은 군집 정보를 Cluster객체로 만들어 Queue에 넣습니다.

6.2 이동

Cluster cur = q.poll();

// 1. 이동
cur.r += dr[cur.dir];
cur.c += dc[cur.dir];
  • 큐에서 하나씩 거내 dr[cur.dir], dc[cur.dir]을 더해 좌표를 갱신합니다.

6.3 약품 처리

if (cur.r == 0 || cur.r == N - 1 || cur.c == 0 || cur.c == N - 1) {
    cur.cnt /= 2;
    if (cur.cnt == 0) continue; // 소멸

    // 방향 반전: 1<->2, 3<->4
    if (cur.dir == 1) cur.dir = 2;
    else if (cur.dir == 2) cur.dir = 1;
    else if (cur.dir == 3) cur.dir = 4;
    else if (cur.dir == 4) cur.dir = 3;
                
    cur.maxCnt = cur.cnt; // 경계에선 혼자이므로 maxCnt 갱신
}
  • 갱신된 좌표가 가장자리라면 cnt/2를 하고, 방향을 반전합니다.
  • 이때 cnt가 0이면 소멸합니다.

6.4 충돌/병합

if (map[cur.r][cur.c] == null) {
    // 해당 칸에 처음 도착
    map[cur.r][cur.c] = new Cluster(cur.r, cur.c, cur.cnt, cur.dir, cur.cnt);
} else {

    // 이미 다른 군집이 있음 -> 병합
    // 이동해온 군집(cur)이 기존 대장보다 크면 방향 뺏어옴
   if (map[cur.r][cur.c].maxCnt < cur.cnt) {
        map[cur.r][cur.c].maxCnt = cur.cnt;
        map[cur.r][cur.c].dir = cur.dir;
    }

    // 전체 미생물 수는 누적
    map[cur.r][cur.c].cnt += cur.cnt;
}
  • 비어있으면 현재 군집을 배치합니다.
  • 이미 군집이 있다면, 기존 maxCnt와 현재 군집의 cnt를 비교해 방향을 결정하고 전체 cnt를 누적합니다.

6.5 반복

Queue<Cluster> nextQ = new LinkedList<>();
 
 for (int r = 0; r < N; r++) {
    for (int c = 0; c < N; c++) {
        if (map[r][c] != null) {
            // 다음 턴의 병합을 위해 maxCnt를 현재 cnt로 리셋
            map[r][c].maxCnt = map[r][c].cnt;
            nextQ.add(map[r][c]);
        }
    }
}
  • 맵에 남은 객체들을 다시 큐에 담고 이 과정을 M번 반복합니다.

6.6 전체 코드

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

public class Solution {
    // 미생물 군집 정보를 담는 클래스
    static class Cluster {
        int r, c, cnt, dir, maxCnt;

        public Cluster(int r, int c, int cnt, int dir, int maxCnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
            this.dir = dir;
            this.maxCnt = maxCnt; // 병합 시 방향 결정을 위한 단일 군집 최대값
        }
    }

    static int N, M, K;
    // 방향: 1(상), 2(하), 3(좌), 4(우)
    static int[] dr = {0, -1, 1, 0, 0};
    static int[] dc = {0, 0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            Queue<Cluster> q = new LinkedList<>();
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int r = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                int cnt = Integer.parseInt(st.nextToken());
                int dir = Integer.parseInt(st.nextToken());
                q.add(new Cluster(r, c, cnt, dir, cnt));
            }

            // M시간 동안 시뮬레이션 진행
            for (int i = 0; i < M; i++) {
                q = moveAndMerge(q);
            }

            // 결과 계산
            int total = 0;
            while (!q.isEmpty()) {
                total += q.poll().cnt;
            }
            System.out.println("#" + tc + " " + total);
        }
    }

    private static Queue<Cluster> moveAndMerge(Queue<Cluster> q) {
        Cluster[][] map = new Cluster[N][N];
        int size = q.size();

        for (int i = 0; i < size; i++) {
            Cluster cur = q.poll();

            // 1. 이동
            cur.r += dr[cur.dir];
            cur.c += dc[cur.dir];

            // 2. 약품 구역(경계) 처리
            if (cur.r == 0 || cur.r == N - 1 || cur.c == 0 || cur.c == N - 1) {
                cur.cnt /= 2;
                if (cur.cnt == 0) continue; // 소멸

                // 방향 반전: 1<->2, 3<->4
                if (cur.dir == 1) cur.dir = 2;
                else if (cur.dir == 2) cur.dir = 1;
                else if (cur.dir == 3) cur.dir = 4;
                else if (cur.dir == 4) cur.dir = 3;
                
                cur.maxCnt = cur.cnt; // 경계에선 혼자이므로 maxCnt 갱신
            }

            // 3. 병합 처리 (2차원 배열 활용)
            if (map[cur.r][cur.c] == null) {
                // 해당 칸에 처음 도착
                map[cur.r][cur.c] = new Cluster(cur.r, cur.c, cur.cnt, cur.dir, cur.cnt);
            } else {
                // 이미 다른 군집이 있음 -> 병합
                // 이동해온 군집(cur)이 기존 대장보다 크면 방향 뺏어옴
                if (map[cur.r][cur.c].maxCnt < cur.cnt) {
                    map[cur.r][cur.c].maxCnt = cur.cnt;
                    map[cur.r][cur.c].dir = cur.dir;
                }
                // 전체 미생물 수는 누적
                map[cur.r][cur.c].cnt += cur.cnt;
            }
        }

        // 4. 처리된 결과를 다시 큐에 담기
        Queue<Cluster> nextQ = new LinkedList<>();
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (map[r][c] != null) {
                    // 다음 턴의 병합을 위해 maxCnt를 현재 cnt로 리셋
                    map[r][c].maxCnt = map[r][c].cnt;
                    nextQ.add(map[r][c]);
                }
            }
        }
        return nextQ;
    }
}

카테고리:

업데이트:

참고

창용 마을 무리의 개수

3 분 소요

1. 문제 접근 방법 및 아이디어 이 문제는 여러 명의 사람이 있고, 그들 사이의 관계가 주어질 때, 총 몇 개의 독립된 그룹이 형성되는가?를 구합니다.

서로소 집합

3 분 소요

1. 문제 접근 방법 및 아이디어 이 문제는 여러 개의 원소가 있을 때, 이들을 합치거나 같은 그룹에 속해 있는지 확인하는 과정을 효율적으로 처리하는 것이 핵심입니다. 독립된 원소 생성 처음에는 모든 숫자가 각각 자기 자신만을 원소로 갖는 집합이 됩니다. ...

파핑파핑 지뢰찾기

6 분 소요

1. 문제 접근 방법 및 아이디어 이 문제의 핵심은 “어떤 칸을 먼저 눌러야 이득인가?”를 판단하는 것입니다.

[모의 SW 역량테스트] 특이한 자석

8 분 소요

1. 문제 접근 방법 및 아이디어 이 문제의 핵심 아이디어는 영향력이 전파되는 방향과 실제 회전 처리를 분리하는 것 입니다. 방향성 확인 특정 자석이 회전할 때, 왼쪽과 오른쪽으로 가며 인접한 자석들과의 접점(맞닿은 극)이 서로 다른지 확인하여 회전 여부를...