메인 게임 루프
├── 턴별 라운드 실행 (order 배열 순서대로)
│ ├── 기물별 순차 행동
│ │ ├── King 행동 (체력 > 0인 경우만)
│ │ │ ├── 8방향 이동 시뮬레이션
│ │ │ │ ├── 각 방향별 보드 딥카피 생성
│ │ │ │ ├── moveKing() 호출: 밀치기 메커니즘
│ │ │ │ │ ├── 목표 칸이 빈 칸: 즉시 이동
│ │ │ │ │ ├── King ↔ King 충돌
│ │ │ │ │ │ ├── 데미지 계산 (같은 색: CA, 다른 색: CB)
│ │ │ │ │ │ ├── 피해 교환 후 체력 업데이트
│ │ │ │ │ │ └── 연쇄 밀치기 시뮬레이션
│ │ │ │ │ ├── King vs Pawn: King이 Pawn을 밀어냄
│ │ │ │ │ └── 보드 밖 처리
│ │ │ │ │ ├── King: 파괴 (체력 0)
│ │ │ │ │ └── Pawn: 특수 처리 (반대편 출현)
│ │ │ │ └── 8개 시뮬레이션 결과 상태 저장
│ │ │ │
│ │ │ ├── 선호도 기반 최적 방향 선택
│ │ │ │ ├── prefW/prefB[기물ID] 우선순위 배열 참조
│ │ │ │ ├── 평가 기준
│ │ │ │ │ ├── 1순위: Pawn 승진거리 최소화
│ │ │ │ │ └── 2순위: x좌표 작은 순
│ │ │ │ └── 이동 불가능한 방향 제외
│ │ │ └── 최종 상태 커밋 (보드, 위치, 체력 업데이트)
│ │ │
│ │ ├── Pawn 행동
│ │ │ ├── 연결 성분 크기 계산 (DFS)
│ │ │ │ ├── 같은 색 Pawn들의 8방향 연결성 탐색
│ │ │ │ └── 연결 성분 크기 반환
│ │ │ │
│ │ │ ├── 연결 성분 > 4개: 그룹 내부 스왑
│ │ │ │ ├── 연결된 모든 Pawn 위치 수집
│ │ │ │ ├── 각 위치별 평가 점수 계산
│ │ │ │ │ ├── 승진거리 (1순위)
│ │ │ │ │ └── 아군 King들과의 거리합 (2순위)
│ │ │ │ ├── 최적 위치 선정
│ │ │ │ └── 현재 위치와 최적 위치 스왑
│ │ │ │
│ │ │ └── 연결 성분 ≤ 4개: 1칸 이동
│ │ │ ├── 8방향 중 빈 칸만 고려
│ │ │ ├── 아군 King들과의 거리합 최소화
│ │ │ ├── 선호도 배열 순서로 방향 선택
│ │ │ └── 이동 실행
│ │ │
│ │ ├── 승진 검사 (매 기물 행동 후)
│ │ │ ├── Pawn 승진 라인 도달 여부 확인
│ │ │ │ ├── 흰 Pawn: 1행 도달 시 Queen 승진
│ │ │ │ └── 검은 Pawn: H행 도달 시 Queen 승진
│ │ │ │
│ │ │ └── 승진 시 onPromote() 실행
│ │ │ ├── Queen 위치에서 상대 King들에게 피해
│ │ │ │ ├── 거리제곱 역비례 피해 공식
│ │ │ │ └── 거리 d에 대해 50/d² 피해
│ │ │ ├── HP ≤ 0인 King들을 보드에서 제거
│ │ │ └── 즉시 게임 종료 (승부 결정)
│ │ │
│ │ └── 다음 기물로 순서 이동
│ │
│ ├── 라운드 완료 시 다음 턴으로
│ └── K턴 완료 또는 승진 발생시 게임 종료
│
└── 최종 보드 상태 출력
├── King: 'K1', 'k2' 등 (체력 > 0인 경우만)
├── Pawn: 'P'/'p' (승진 라인에서는 'Q'/'q')
└── 빈 칸: '.'
핵심 알고리즘 세부 구조
1. 물리 시뮬레이션 엔진
2. 연결 성분 탐색 (DFS)
3. 평가 함수 시스템
4. 상태 관리 시스템
5. 승진 시스템
복잡도 분석
시간 복잡도:
King 행동: O(8 × 보드크기) - 8방향 시뮬레이션
Pawn 행동: O(보드크기) - DFS 연결성분 + 이동 평가
전체 턴: O(K × 기물수 × 보드크기)
공간 복잡도:
보드 상태: O(H × W)
기물 정보: O(기물수)
DFS 스택: O(보드크기)
특이점:
물리 시뮬레이션: 밀치기 연쇄반응으로 인한 복잡한 상태 변화
전략적 AI: 선호도 배열 기반의 휴리스틱 의사결정
동적 종료: 승진 발생시 즉시 게임 종료
상태 롤백: 시뮬레이션 후 최적 선택을 위한 딥카피 활용
코드트리 갬빗은 세 문제 중 가장 복잡한 전략 시뮬레이션 게임으로, 물리 엔진 + AI 의사결정 + 복잡한 상태 관리가 모두 결합된 구조입니다.
코드
미생물 연구 프로세스 플로우차트
순차적 미생물 배치 및 상호작용 시뮬레이션
핵심 알고리즘 구조
1. 미생물 충돌 및 분할 시스템
2. 전체 재배치 시스템 (Compaction)
3. 인접성 및 상호작용 계산
자료구조 및 상태 관리
1. 핵심 자료구조
2. 연산 복잡도
실제 문제의 특징:
기하학적 배치: 직사각형 미생물의 순차적 배치
동적 분할: 충돌로 인한 미생물 분리 및 제거
공간 최적화: 재배치를 통한 격자 공간 압축
상호작용 계산: 인접 미생물들 간의 상호작용 점수
이 문제는 계산 기하학 + 동적 그래프 + 공간 최적화가 결합된 복합적 시뮬레이션입니다.
코드
민트초코우유 플로우차트
T일간 요리 집단 행동 시뮬레이션
핵심 알고리즘 구조
1. 그룹 형성 및 리더십 시스템
2. 음식 융합 시스템
3. 전파 우선순위 시스템
4. 전파 메커니즘
시뮬레이션 특성
1. 사회 역학
2. 문화 전파 모델
알고리즘 복잡도:
시간 복잡도: O(T × N² × 그룹수)
공간 복잡도: O(N² + 그룹수)
특이점:
사회학적 시뮬레이션: 리더십, 위계질서, 집단 역학
문화 융합 모델: 창조적 음식 조합 생성
운명론적 방향성: 신앙심에 따른 확정적 행동
우선순위 기반 행동: 복잡한 다중 기준 정렬
이 문제는 사회학 + 문화인류학 + 게임이론이 결합된 독특한 집단 행동 시뮬레이션입니다.
코드
메두사와 전사들 실제 구조 플로우차트
턴제 추격 및 생존 게임
핵심 알고리즘 구조
1. 복잡한 시야 시스템 (3갈래 확산 + 가려짐)
2. 전사 이동 전략 (거리 단축 우선)
3. 메두사 최적 경로 탐색
게임 역학 및 특성
1. 비대칭 게임플레이
2. 전략적 요소
알고리즘 복잡도:
시간 복잡도: O(턴수 × (N² + M×이동횟수))
공간 복잡도: O(N² + M)
특이점:
복잡한 시야 시스템: 3갈래 확산 + 동적 가려짐 처리
거리 기반 이동: 전사들의 지능적 추격 알고리즘
비대칭 게임플레이: 서로 다른 능력과 목표
실시간 전략: 매 턴 최적 선택이 승부 결정
메두사와 전사들은 비대칭 실시간 전략 게임의 특성을 가진 복잡한 추격 시뮬레이션입니다.
코드
고대문명 유적탐사 프로세스 플로우차트
게임 루프 (최대 K턴)
핵심 알고리즘 구조
1. 회전 시뮬레이션
2. 연결 그룹 탐색 (BFS)
3. 우선순위 결정
단순화 개선안
현재 코드가 복잡한 이유:
시뮬레이션과 실행을 분리: isReal 플래그 등 복잡한 구조
과도한 함수 분리: rotate, get, simulateRotation 등
불필요한 최적화: TreeSet 사용, 복잡한 Point 클래스
단순화된 구조:
훨씬 단순하게 만들 수 있지만, 현재 구조도 동작은 정상적으로 하므로 큰 문제는 아닙니다.
코드
마법의 숲 탐색 프로세스 플로우차트
메인 게임 루프 (K명의 정령)
핵심 물리 시뮬레이션
1. 골렘 이동 메커니즘
2. 정령 탐사 네트워크
3. 좌표계 관리
상태 관리 체계
1. 골렘 상태 추적
2. 이동 가능성 검사
3. 출구 시스템
알고리즘 복잡도
시간 복잡도:
골렘 이동: O(K × R) - K개 골렘, 최대 R번 남쪽 이동
정령 탐사: O(K × R × C) - K번의 BFS, 각 BFS는 O(R×C)
전체: O(K × R × C)
공간 복잡도:
보드: O(R × C)
골렘 정보: O(K)
BFS 방문 배열: O(R × C)
전체: O(R × C + K)
마법의 숲은 고대문명보다 복잡한 물리 시뮬레이션 (골렘 회전이동)과 네트워크 탐색 (정령 이동)이 결합된 구조입니다. 특히 골렘간 연결성을 통한 정령의 최적 경로 탐색이 핵심입니다.
코드
미지의 공간 탈출 프로세스 플로우차트
2단계 탈출 시뮬레이션
핵심 알고리즘 구조
1. 3D 큐브 면간 이동 시스템
2. 시간 이상 현상 확산 모델
알고리즘 복잡도:
Phase 1: O(5 × M² × 최대경로길이) - 3D BFS
Phase 2: O(N² × 최대시간) - 시간 종속 2D BFS
전체: O(5M² + N²T) (T는 최대 탈출 시간)
특이점:
3D 기하학: 복잡한 면간 좌표 변환
시간 종속 그래프: 동적으로 변하는 장애물
2단계 최적화: 각 단계별 독립적 최적 경로
복합 제약 조건: 공간적 + 시간적 제약 동시 고려
미지의 공간 탈출은 3D 기하학 + 시간 종속 그래프 탐색이 결합된 매우 독특한 구조의 문제입니다.
moveKing(현재King, 방향):
├── 목표 위치 계산
├── 목표 칸 상태별 처리
│ ├── 빈 칸: 즉시 이동 완료
│ ├── King 충돌
│ │ ├── 데미지 계산 및 적용
│ │ ├── 밀치기 연쇄 반응
│ │ │ ├── 밀려난 King의 새 위치 계산
│ │ │ ├── 그 위치에서 또 다른 충돌 확인
│ │ │ └── 보드 밖으로 나갈 때까지 재귀적 처리
│ │ └── 최종 위치들 업데이트
│ └── Pawn 충돌: Pawn 밀치기 처리
└── 보드 경계 처리 (파괴 vs 특수이동)
getComponentSize(PawnID):
├── 해당 Pawn 위치에서 DFS 시작
├── 8방향 인접 칸 탐색
│ ├── 같은 색 Pawn인지 확인
│ ├── 미방문 칸인지 확인
│ └── 조건 만족시 재귀적 DFS 호출
├── 방문한 모든 Pawn 개수 카운트
└── 연결 성분 크기 반환
King 이동 평가:
├── 1순위: 이동 가능 여부
├── 2순위: 아군 Pawn 승진거리 최소화
│ ├── 각 아군 Pawn의 승진 라인까지 거리 계산
│ └── 거리 합계가 작을수록 선호
├── 3순위: x좌표 작은 순 (동점시)
└── 선호도 배열 순서 적용
Pawn 이동 평가:
├── 1순위: 승진거리 최소화
├── 2순위: 아군 King들과의 거리합 최소화
└── 선호도 배열 순서 적용
게임 상태 구조:
├── 보드 상태: A[H][W] (기물 배치)
├── 위치 정보
│ ├── wPos[]/bPos[]: 각 기물의 (r,c) 좌표
│ └── wHP[]/bHP[]: 각 King의 체력
├── 선호도 배열: prefW[]/prefB[] (행동 우선순위)
└── 순서 배열: order[] (기물 행동 순서)
onPromote(Queen위치, 상대색):
├── 상대 King들 스캔
├── 각 King별 피해 계산
│ ├── 거리 d = |qr-kr| + |qc-kc|
│ ├── 피해량 = 50 / (d × d)
│ └── King 체력에서 피해량 차감
├── 체력 ≤ 0인 King들 제거
└── 게임 종료 플래그 설정
import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;
public class Main {
// ====== 좌표/쌍 ======
static class Pair {
int x, y; // x=열(가로), y=행(세로) - 통상적 좌표계
Pair(int x, int y){ this.x = x; this.y = y; }
@Override public boolean equals(Object o){
if (this == o) return true;
if (!(o instanceof Pair)) return false;
Pair p = (Pair)o;
return x == p.x && y == p.y;
}
@Override public int hashCode(){ return Objects.hash(x, y); }
}
// ====== 전역 파라미터 ======
static int H, W, N, K, CA, CB; // CA/CB = 데미지 계수
static final int INF = 0x3f3f3f3f;
// 8방 (상, 우상, 우, 우하, 하, 좌하, 좌, 좌상) — 입력 선호 문자열은 0..7 인덱스
// 통상적 좌표계: dx=열 변화량(가로), dy=행 변화량(세로)
static final int[] dx = { 0, 1, 1, 1, 0,-1,-1,-1}; // x(열) 변화량
static final int[] dy = {-1,-1, 0, 1, 1, 1, 0,-1}; // y(행) 변화량
// ====== 보드/상태 ======
// 보드: A[y][x] = A[행][열] (통상적 2차원 배열 접근)
static int[][] A;
// 흰/검 각 기물 위치: 인덱스 1..N은 King, N+1은 Pawn
static Pair[] wPos, bPos;
// 흰/검 King 체력: 1..N (Pawn은 HP 없음)
static int[] wHP, bHP;
// 이동 우선순위 (각 기물 인덱스 1..N+1 에 대해 길이8 방향 인덱스)
static int[][] prefW, prefB;
// 실행 순서 (입력 순서 그대로, 부호/ID로 구분)
// +i : White King i, -(i) : Black King i
// +(N+1): White Pawn, -(N+1): Black Pawn
static int[] order;
// 유틸
static boolean OOB(int x, int y){ return (x < 1 || x > W || y < 1 || y > H); }
static boolean isWhite(int o){ return o > 0; }
static int sqr(int v){ return v*v; }
static int dist2(Pair a, Pair b){ return sqr(a.x - b.x) + sqr(a.y - b.y); }
// 프로모션까지 남은 거리 (흰: 1행, 검: H행)
static int promoDist(boolean white, int y){
return white ? (y - 1) : (H - y);
}
// 이름을 정수 ID로 매핑: "K3"→+3, "k2"→-2, "P"→+(N+1), "p"→-(N+1)
static int readPieceCode(String s){
char c = s.charAt(0);
if (c == 'P') return (N+1);
if (c == 'p') return -(N+1);
int id = Integer.parseInt(s.substring(1));
if (c == 'K') return id;
if (c == 'k') return -id;
return 0; // should not happen
}
// HP 접근/설정
static int getHP(int o){
int id = Math.abs(o);
if (id > N) return 0; // Pawn
return isWhite(o) ? wHP[id] : bHP[id];
}
static void setHP(int o, int val){
int id = Math.abs(o);
if (id > N) return; // Pawn 없음
if (isWhite(o)) wHP[id] = val; else bHP[id] = val;
}
static Pair getPos(int o){
int id = Math.abs(o);
return isWhite(o) ? wPos[id] : bPos[id];
}
static void setPos(int o, Pair p){
int id = Math.abs(o);
if (isWhite(o)) wPos[id] = p; else bPos[id] = p;
}
// 체스판 Deep Copy
static int[][] copyBoard(int[][] src){
int[][] dst = new int[H+1][W+1];
for (int i=1;i<=H;i++) System.arraycopy(src[i], 1, dst[i], 1, W);
return dst;
}
static Pair[] copyPairs(Pair[] src){
Pair[] dst = new Pair[src.length];
for (int i=1;i<src.length;i++){
if (src[i] != null) {
Pair p = src[i];
dst[i] = new Pair(p.x, p.y); // x, y 순서
}
}
return dst;
}
static int[] copyArr(int[] a){
int[] b = new int[a.length];
System.arraycopy(a, 0, b, 0, a.length);
return b;
}
// 상태 스냅샷
static class State {
int[][] B;
Pair[] wP, bP;
int[] wH, bH;
State deepCopy(){
State s = new State();
s.B = copyBoard(B);
s.wP = copyPairs(wP);
s.bP = copyPairs(bP);
s.wH = copyArr(wH);
s.bH = copyArr(bH);
return s;
}
}
// DFS (8방) — 같은 색 연결 성분 크기 구하기(폰 이동 규칙에서 사용)
static void dfs(int x, int y, int colorSign, boolean[][] vis, HashSet<Pair> acc){
if (OOB(x,y)) return;
int t = A[y][x]; // A[행][열] 접근
if (t == 0) return;
if ((t > 0) != (colorSign > 0)) return;
if (vis[y][x]) return; // vis[행][열] 접근
vis[y][x] = true;
Pair cur = new Pair(x,y); // (열, 행) 순서
acc.add(cur);
for (int d=0; d<8; d++){
dfs(x + dx[d], y + dy[d], colorSign, vis, acc);
}
}
// === 승진 처리: 승진한 쪽의 퀸 위치에서 상대 King들에게 거리제곱만큼 피해 ===
static void onPromote(boolean white){
Pair queen = (white ? wPos[N+1] : bPos[N+1]); // 폰 위치 = 퀸 위치로 취급
for (int i=1;i<=N;i++){
int hp = (white ? bHP[i] : wHP[i]);
if (hp > 0){
Pair enemy = (white ? bPos[i] : wPos[i]);
hp -= dist2(queen, enemy);
if (white) bHP[i] = hp; else wHP[i] = hp;
if (hp <= 0){
// 보드에서 제거
A[enemy.y][enemy.x] = 0; // A[행][열]
}
}
}
}
// === King 이동 시뮬레이션: dr 방향으로 '밀치기' 포함 ===
static boolean moveKing(int o, int dr, State S){
Pair p = (isWhite(o) ? S.wP[Math.abs(o)] : S.bP[Math.abs(o)]);
int x = p.x, y = p.y; // x=열, y=행
int nx = x + dx[dr], ny = y + dy[dr];
if (OOB(nx,ny)) return false;
// 제자리 비우기
S.B[y][x] = 0; // S.B[행][열]
x = nx; y = ny;
// 밀치기 루프
while (true){
int t = (OOB(x,y) ? 0 : S.B[y][x]);
// 보드 밖으로 밀린 경우
if (OOB(x,y)){
if (Math.abs(o) == N+1){ // Pawn이 밖으로 나가면: 직전 칸의 말을 제거
int px = x - dx[dr], py = y - dy[dr];
int pv = S.B[py][px];
setHPInState(S, pv, 0);
S.B[py][px] = o;
setPosInState(S, o, new Pair(px, py));
return true;
} else { // King이 밖으로 나가면: 본인 파괴
setHPInState(S, o, 0);
setPosInState(S, o, new Pair(x, y)); // 경계 밖 좌표 기록만(의미X)
return true;
}
}
if (t == 0){
S.B[y][x] = o;
setPosInState(S, o, new Pair(x, y));
return true;
}
// o가 King인지 Pawn인지에 따라
if (Math.abs(o) <= N){ // King
// 상대 Pawn(상대 N+1)이 있는 칸으로는 진입 불가
if (t == (N+1) * (isWhite(o)? -1 : 1)) return false;
if (Math.abs(t) <= N){ // King ↔ King 밀치기: 피해 후 교대 이동
int hp = getHPInState(S, t);
hp -= ( (o>0) == (t>0) ? CA : CB ); // 같은 색/다른 색 구분 피해
setHPInState(S, t, hp);
S.B[y][x] = o;
setPosInState(S, o, new Pair(x, y));
if (hp <= 0) return true;
// 다음 타자는 t가 되어, 한 칸 더 같은 방향으로 밀린다
o = t;
x += dx[dr]; y += dy[dr];
} else { // King이 Pawn을 밀치면: Pawn을 한 칸 더 민다
S.B[y][x] = o;
setPosInState(S, o, new Pair(x, y));
o = t; // 이제 대상(o)이 Pawn이 되어 계속 진행
x += dx[dr]; y += dy[dr];
}
} else { // o가 Pawn
if (Math.abs(t) == N+1){ // 같은 Pawn이면: 직전 칸의 말 제거하고 Pawn 정지
int px = x - dx[dr], py = y - dy[dr];
int pv = S.B[py][px];
setHPInState(S, pv, 0);
S.B[py][px] = o;
setPosInState(S, o, new Pair(px, py));
return true;
} else {
// Pawn이 King을 밀면: 그 King 제거하고 Pawn이 그 자리에 선다
setHPInState(S, t, 0);
S.B[y][x] = o;
setPosInState(S, o, new Pair(x, y));
return true;
}
}
}
}
// === State 기반 HP/좌표 헬퍼 ===
static int getHPInState(State S, int o){
if (o == 0) return 0;
int id = Math.abs(o);
if (id > N) return 0;
return (o>0) ? S.wH[id] : S.bH[id];
}
static void setHPInState(State S, int o, int v){
if (o == 0) return;
int id = Math.abs(o);
if (id > N) return;
if (o>0) S.wH[id] = v; else S.bH[id] = v;
}
static void setPosInState(State S, int o, Pair p){
int id = Math.abs(o);
if (o>0) S.wP[id] = p; else S.bP[id] = p;
}
// === King 한 번 이동(의사결정 포함) ===
static void stepKing(int o){
// 체력 0 이면 이동하지 않음
if (getHP(o) <= 0) return;
// 8방향 각각 시뮬(딥카피)
State baseline = new State();
baseline.B = copyBoard(A);
baseline.wP = copyPairs(wPos);
baseline.bP = copyPairs(bPos);
baseline.wH = copyArr(wHP);
baseline.bH = copyArr(bHP);
boolean[] can = new boolean[8];
State[] cand = new State[8];
for (int d=0; d<8; d++){
State S = baseline.deepCopy();
can[d] = moveKing(o, d, S);
cand[d] = S;
}
// 선호도 순대로 가장 좋은 방향 선택
int idx = Math.abs(o);
int bestDir = -1;
int bestDst = INF;
int bestX = INF;
int[] pref = (o>0) ? prefW[idx] : prefB[idx];
for (int k=0; k<8; k++){
int dr = pref[k];
if (!can[dr]) continue;
State S = cand[dr];
Pair pawn = (o>0) ? S.wP[N+1] : S.bP[N+1];
int dst = promoDist(o>0, pawn.y);
int x = pawn.x; // x좌표 (열)
if (dst < bestDst || (dst == bestDst && x < bestX)){
bestDst = dst; bestX = x; bestDir = dr;
}
}
if (bestDir == -1) return; // 어디도 못 움직임
// 최종 채택 상태로 커밋
State S = cand[bestDir];
A = S.B;
wPos = S.wP; bPos = S.bP;
wHP = S.wH; bHP = S.bH;
}
// === Pawn 한 번 이동 ===
static void stepPawn(int o){
Pair p = getPos(o);
int ox = p.x, oy = p.y; // x=열, y=행
// 같은 색 연결 성분 크기
boolean[][] vis = new boolean[H+1][W+1];
HashSet<Pair> comp = new HashSet<>();
dfs(ox, oy, o, vis, comp);
if (comp.size() > 4){
// 그룹이 크면: 승진에 가까워지도록 같은 색 내부에서 '스왑'
Pair best = null;
int bestD = INF;
int bestSum = INF;
for (Pair v : comp){
int dst = promoDist(o>0, v.y);
int sum = 0;
for (int i=1;i<=N+1;i++){
// 내 편 King(살아있는) + Pawn(N+1)까지 거리합
if (i == N+1 || getHP( (o>0? i : -i) ) > 0){
Pair q = getPos( o>0 ? i : -i );
sum += dist2(v, q);
}
}
if (dst < bestD || (dst == bestD && sum < bestSum)){
best = v; bestD = dst; bestSum = sum;
}
}
int k = A[best.y][best.x]; // A[행][열]
if (k != o){
// 위치 스왑
Pair kp = getPos(k);
int tmp = A[oy][ox];
A[oy][ox] = A[kp.y][kp.x];
A[kp.y][kp.x] = tmp;
setPos(o, new Pair(kp.x, kp.y));
setPos(k, new Pair(ox, oy));
}
} else {
// 그룹이 작으면: 비어있는 칸으로 1칸 이동(선호도: Pawn용=N+1)
int bestDir = -1;
int bestScore = INF;
int[] pref = (o>0) ? prefW[N+1] : prefB[N+1];
for (int k=0; k<8; k++){
int dr = pref[k];
int nx = ox + dx[dr], ny = oy + dy[dr];
if (OOB(nx,ny) || A[ny][nx] != 0) continue;
// 자신의 King들과의 거리합이 최소가 되는 방향
int sum = 0;
for (int i=1;i<=N;i++){
if (getHP( (o>0? i : -i) ) > 0){
Pair q = getPos( o>0 ? i : -i );
sum += dist2(new Pair(nx,ny), q);
}
}
if (sum < bestScore){
bestScore = sum; bestDir = dr;
}
}
if (bestDir != -1){
A[oy][ox] = 0;
int nx = ox + dx[bestDir], ny = oy + dy[bestDir];
A[ny][nx] = o;
setPos(o, new Pair(nx,ny));
}
}
}
// === 한 기물(o) 차례 처리: King/Pawn 구분 ===
// 반환값: true → 아직 승진 전, false → 방금 승진(또는 이미 승진 상태)
static boolean stepOne(int o){
if (Math.abs(o) <= N){
// King: 체력 0 이하면 스킵
if (getHP(o) > 0) stepKing(o);
} else {
// Pawn
stepPawn(o);
}
// 승진 여부 체크
Pair myPawn = getPos( isWhite(o) ? (N+1) : -(N+1) );
int d = promoDist(isWhite(o), myPawn.y);
return d > 0;
}
// === 출력 ===
static void printBoard(){
StringBuilder sb = new StringBuilder();
for (int i=1;i<=H;i++){
for (int j=1;j<=W;j++){
int v = A[i][j]; // A[행][열]
if (v == 0){
sb.append('.');
} else if (v > 0 && v <= N){
sb.append('K').append(v);
} else if (v < 0 && -v <= N){
sb.append('k').append(-v);
} else if (v == (N+1)){
sb.append( (i==1) ? 'Q' : 'P' );
} else if (v == -(N+1)){
sb.append( (i==H) ? 'q' : 'p' );
}
if (j < W) sb.append(' ');
}
sb.append('\n');
}
System.out.print(sb);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 입력
H = sc.nextInt();
W = sc.nextInt();
N = sc.nextInt();
K = sc.nextInt();
CA = sc.nextInt();
CB = sc.nextInt();
int totalPieces = 2*N + 2;
// 보드/상태 초기화
A = new int[H+1][W+1];
wPos = new Pair[N+2];
bPos = new Pair[N+2];
for (int i=1;i<=N+1;i++){
wPos[i] = new Pair(0,0);
bPos[i] = new Pair(0,0);
}
wHP = new int[N+1];
bHP = new int[N+1];
order = new int[totalPieces];
// 기물 입력
for (int i=0;i<totalPieces;i++){
String name = sc.next();
int r = sc.nextInt(); // 행
int c = sc.nextInt(); // 열
int id = readPieceCode(name); // +i/-i, +-(N+1)
order[i] = id;
A[r][c] = id; // A[행][열]
if (id > 0){
int idx = Math.abs(id);
wPos[idx] = new Pair(c, r); // Pair(열, 행)
} else {
int idx = Math.abs(id);
bPos[idx] = new Pair(c, r); // Pair(열, 행)
}
}
// 방향 선호 (N+1줄: King1..N + Pawn)
prefW = new int[N+2][8];
prefB = new int[N+2][8];
for (int i=1;i<=N+1;i++){
String s = sc.next(); // 길이 8, 각 글자 '0'..'7'
for (int k=0;k<8;k++) prefW[i][k] = s.charAt(k) - '0';
}
for (int i=1;i<=N+1;i++){
String s = sc.next();
for (int k=0;k<8;k++) prefB[i][k] = s.charAt(k) - '0';
}
// HP
for (int i=1;i<=N;i++) wHP[i] = sc.nextInt();
for (int i=1;i<=N;i++) bHP[i] = sc.nextInt();
// 시뮬레이션: 최대 K턴, 매 턴 order 순서대로
outer:
for (int t=0; t<K; t++){
for (int o : order){
boolean notPromoted = stepOne(o);
if (!notPromoted){
// 방금 승진 → 퀸 딜 후 즉시 종료
onPromote(o > 0);
break outer;
}
}
}
printBoard();
}
}
미생물 배치 시스템 (Q개 미생물 순차 처리)
├── 미생물별 순차 배치 프로세스
│ ├── 미생물 추가 단계
│ │ ├── 입력 처리
│ │ │ ├── 직사각형 영역 정의 [r1, r2) × [c1, c2)
│ │ │ ├── 새 미생물 객체 생성 (ID = 현재 순서)
│ │ │ └── 영역 내 모든 좌표를 미생물에 추가
│ │ │
│ │ ├── 기존 미생물과의 충돌 처리
│ │ │ ├── 새 영역과 겹치는 모든 칸 스캔
│ │ │ ├── 기존 미생물이 차지한 칸 발견시
│ │ │ │ ├── 기존 미생물에서 해당 좌표 제거
│ │ │ │ ├── 영향받는 미생물 ID 수집 (affected 집합)
│ │ │ │ └── 보드에서 새 미생물 ID로 덮어쓰기
│ │ │ └── 새 미생물이 모든 충돌 영역 점유
│ │ │
│ │ └── 분리된 미생물 검사 및 제거
│ │ ├── 영향받은 각 미생물별 연결성 검사
│ │ ├── BFS로 4방향 연결성 확인
│ │ │ ├── 시작점: 남은 좌표 중 임의의 점
│ │ │ ├── 탐색: 4방향 인접한 같은 미생물 좌표
│ │ │ └── 결과: 연결된 모든 좌표 집합
│ │ ├── 연결성 판단
│ │ │ ├── 방문된 좌표 수 == 전체 좌표 수: 연결됨 (유지)
│ │ │ └── 방문된 좌표 수 < 전체 좌표 수: 분리됨 (제거)
│ │ └── 분리된 미생물 완전 제거
│ │ ├── removed 플래그 설정
│ │ ├── 보드에서 모든 좌표를 0으로 변경
│ │ └── 미생물 좌표 집합 초기화
│ │
│ ├── 전체 미생물 재배치 단계 (rearrange)
│ │ ├── 생존 미생물 우선순위 정렬
│ │ │ ├── 1순위: 크기 큰 순 (size 내림차순)
│ │ │ └── 2순위: ID 작은 순 (id 오름차순)
│ │ │
│ │ ├── 순차적 재배치 실행
│ │ │ ├── 빈 보드(newBoard) 생성
│ │ │ ├── 우선순위 순서대로 각 미생물 처리
│ │ │ │ ├── 미생물 모양 정규화
│ │ │ │ │ ├── 좌표들을 행→열 순으로 정렬
│ │ │ │ │ ├── 가장 작은 좌표를 기준점으로 설정
│ │ │ │ │ └── 모든 좌표를 상대좌표로 변환
│ │ │ │ ├── 배치 위치 탐색 (행→열 순)
│ │ │ │ │ ├── (0,0)부터 시작하여 순차 탐색
│ │ │ │ │ ├── 각 위치에서 모양이 들어갈 수 있는지 확인
│ │ │ │ │ │ ├── 모든 상대좌표가 보드 범위 내인가
│ │ │ │ │ │ └── 모든 상대좌표 위치가 비어있는가
│ │ │ │ │ └── 조건 만족시 해당 위치에 배치
│ │ │ │ └── 배치 완료 처리
│ │ │ │ ├── newBoard에 미생물 ID 기록
│ │ │ │ ├── 미생물 좌표 집합 업데이트
│ │ │ │ └── 다음 미생물로 진행
│ │ │ └── 배치 불가능한 미생물 제거
│ │ │ ├── 적절한 위치를 찾지 못한 경우
│ │ │ ├── removed 플래그 설정
│ │ │ └── 좌표 집합 초기화
│ │ │
│ │ └── 보드 상태 업데이트 (board = newBoard)
│ │
│ └── 결과 계산 및 출력
│ ├── 인접 미생물 쌍 탐색
│ │ ├── 현재까지 배치된 모든 미생물 쌍 검사
│ │ ├── 각 쌍(id1, id2)에 대해 인접성 확인
│ │ │ ├── 첫 번째 미생물의 모든 좌표에서
│ │ │ ├── 4방향 인접 칸 확인
│ │ │ └── 두 번째 미생물 좌표와 일치하는지 검사
│ │ └── 인접한 쌍들의 상호작용 값 계산
│ │
│ ├── 상호작용 점수 합산
│ │ ├── 각 인접 쌍에 대해: size1 × size2
│ │ ├── 중복 방지: (id1, id2) 쌍당 한 번만 계산
│ │ └── 모든 상호작용 점수 누적 합산
│ │
│ └── 현재 단계 결과 출력
│
└── 최종 시뮬레이션 완료
충돌 처리 알고리즘:
├── 새 미생물 배치시 기존 미생물과 겹치는 영역 처리
│ ├── 영역 스캔: [r1, r2) × [c1, c2) 모든 칸 확인
│ ├── 충돌 감지: board[i][j] != 0인 칸 발견
│ ├── 점유권 이전: 기존 미생물에서 좌표 제거 → 새 미생물에 추가
│ └── 영향받은 미생물 목록 수집
│
├── 분리 검사 (4방향 연결성 BFS)
│ ├── 각 영향받은 미생물별 독립 검사
│ ├── BFS 탐색
│ │ ├── 시작점: 미생물의 첫 번째 좌표
│ │ ├── 확장: 4방향 인접하고 같은 미생물인 좌표
│ │ └── 종료: 더 이상 확장할 수 없을 때
│ └── 연결성 판정
│ ├── 방문 좌표 수 == 전체 좌표 수: 하나의 연결체
│ └── 방문 좌표 수 < 전체 좌표 수: 분리됨 → 제거
│
└── 제거 처리
├── removed 플래그 true 설정
├── 보드에서 모든 해당 좌표를 0으로 초기화
└── 미생물 객체의 좌표 집합 clear()
재배치 알고리즘:
├── 우선순위 기반 정렬
│ ├── 1차 기준: 크기 큰 순 (points.size() 내림차순)
│ ├── 2차 기준: ID 작은 순 (미생물 ID 오름차순)
│ └── 목적: 큰 미생물이 좋은 자리를 먼저 차지
│
├── 모양 정규화 (Shape Normalization)
│ ├── 좌표 정렬: (r,c) 사전식 순서 정렬
│ ├── 기준점 설정: 가장 작은 (r,c) 좌표
│ ├── 상대좌표 변환: 모든 좌표 - 기준점
│ └── 정규화된 모양: 항상 (0,0)에서 시작하는 상대 좌표 집합
│
├── 배치 위치 탐색
│ ├── 탐색 순서: (0,0) → (0,1) → ... → (0,N-1) → (1,0) → ...
│ ├── 배치 가능성 검사
│ │ ├── 범위 확인: 모든 상대좌표 + 기준점이 [0,N) 범위 내
│ │ ├── 충돌 확인: 해당 위치들이 모두 비어있는지
│ │ └── 조건 만족시 즉시 배치 후 다음 미생물로
│ └── 배치 불가시 미생물 제거
│
└── 상태 업데이트
├── newBoard에 미생물 ID 기록
├── 미생물 객체의 좌표 집합 갱신
└── 전역 board를 newBoard로 교체
상호작용 점수 계산:
├── 모든 미생물 쌍 검사 (id1 < id2)
│ ├── 양쪽 미생물 모두 존재하고 제거되지 않았는지 확인
│ ├── 크기가 0보다 큰지 확인
│ └── 인접성 검사 수행
│
├── 인접성 판정 알고리즘
│ ├── 첫 번째 미생물의 모든 좌표 (r,c)에 대해
│ ├── 4방향 인접 좌표 (nr,nc) 계산
│ │ ├── 상: (r-1,c), 하: (r+1,c)
│ │ ├── 좌: (r,c-1), 우: (r,c+1)
│ │ └── 경계 확인: 0 ≤ nr,nc < N
│ ├── 두 번째 미생물이 해당 좌표를 포함하는지 확인
│ └── 하나라도 인접하면 true 반환
│
├── 상호작용 점수 누적
│ ├── 인접한 각 쌍: score += size1 × size2
│ ├── 중복 방지: seen 집합으로 "id1,id2" 문자열 관리
│ └── 총합 계산 후 출력
│
└── 단계별 누적 출력
├── 매 미생물 추가 후 즉시 계산
├── 현재까지 배치된 미생물들만 고려
└── 동적으로 변화하는 상호작용 추적
Microbe 클래스:
├── TreeSet<Point> points: 정렬된 좌표 집합
├── boolean removed: 제거 여부 플래그
├── 메소드들: addPoint, removePoint, size, contains, start, clear
Point 클래스:
├── int r, c: 행, 열 좌표
├── Comparable 구현: (r,c) 사전식 순서
├── equals/hashCode: 집합 연산 지원
전역 상태:
├── int[][] board: N×N 격자 (미생물 ID 저장)
├── Map<Integer, Microbe> microbes: ID → 미생물 객체 매핑
├── 방향 벡터: dr[], dc[] (상하좌우)
import java.util.*;
import java.io.*;
public class Main {
static int N, Q;
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int[][] board;
static class Point implements Comparable<Point> {
int r, c;
Point(int r, int c) { this.r = r; this.c = c; }
@Override
public int compareTo(Point o) {
if (r != o.r) return r - o.r;
return c - o.c;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Point)) return false;
Point p = (Point) o;
return r == p.r && c == p.c;
}
@Override
public int hashCode() {
return Objects.hash(r, c);
}
}
static class Microbe {
TreeSet<Point> points = new TreeSet<>();
boolean removed = false;
void addPoint(int r, int c) { points.add(new Point(r, c)); }
void removePoint(int r, int c) { points.remove(new Point(r, c)); }
int size() { return points.size(); }
boolean contains(int r, int c) { return points.contains(new Point(r, c)); }
Point start() { return points.isEmpty() ? null : points.first(); }
void clear() { points.clear(); }
}
static Map<Integer, Microbe> microbes = new HashMap<>();
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());
board = new int[N][N]; // 0-based, 0..N-1
for (int id = 1; id <= Q; id++) {
st = new StringTokenizer(br.readLine());
int r1 = Integer.parseInt(st.nextToken());
int c1 = Integer.parseInt(st.nextToken());
int r2 = Integer.parseInt(st.nextToken());
int c2 = Integer.parseInt(st.nextToken());
Microbe m = new Microbe();
// [r1, r2), [c1, c2)
for (int i = r1; i < r2; i++) {
for (int j = c1; j < c2; j++) {
m.addPoint(i, j);
}
}
microbes.put(id, m);
addMicrobe(id, r1, c1, r2, c2);
rearrange();
printResult(id);
}
}
static void addMicrobe(int id, int r1, int c1, int r2, int c2) {
Set<Integer> affected = new HashSet<>();
for (int i = r1; i < r2; i++) {
for (int j = c1; j < c2; j++) {
if (board[i][j] != 0) {
int old = board[i][j];
if (!microbes.get(old).removed) {
microbes.get(old).removePoint(i, j);
affected.add(old);
}
}
board[i][j] = id;
}
}
// 분리 검사
for (int old : affected) {
Microbe m = microbes.get(old);
if (m.size() == 0 || !isOnePiece(m)) {
m.removed = true;
for (Point p : new ArrayList<>(m.points)) {
board[p.r][p.c] = 0;
}
m.clear();
}
}
}
static boolean isOnePiece(Microbe m) {
if (m == null || m.removed || m.points.isEmpty()) return false;
Queue<Point> q = new LinkedList<>();
Set<Point> visited = new HashSet<>();
Point start = m.start();
q.add(start);
visited.add(start);
while (!q.isEmpty()) {
Point cur = q.poll();
for (int d = 0; d < 4; d++) {
int nr = cur.r + dr[d];
int nc = cur.c + dc[d];
Point np = new Point(nr, nc);
if (m.points.contains(np) && !visited.contains(np)) {
visited.add(np);
q.add(np);
}
}
}
return visited.size() == m.size();
}
static void rearrange() {
int[][] newBoard = new int[N][N];
List<int[]> order = new ArrayList<>();
for (int id = 1; id <= Q; id++) {
Microbe m = microbes.get(id);
if (m != null && !m.removed && m.size() > 0) {
order.add(new int[]{id, m.size()});
}
}
order.sort((a, b) -> {
if (a[1] != b[1]) return b[1] - a[1];
return a[0] - b[0];
});
for (int[] arr : order) {
int id = arr[0];
Microbe m = microbes.get(id);
if (m == null) continue;
List<Point> shape = new ArrayList<>(m.points);
shape.sort((p1, p2) -> {
if (p1.r != p2.r) return p1.r - p2.r;
return p1.c - p2.c;
});
Point sp = shape.get(0);
List<Point> norm = new ArrayList<>();
for (Point p : shape) {
norm.add(new Point(p.r - sp.r, p.c - sp.c));
}
boolean placed = false;
for (int i = 0; i < N && !placed; i++) {
for (int j = 0; j < N && !placed; j++) {
boolean can = true;
for (Point p : norm) {
int nr = i + p.r, nc = j + p.c;
if (OOB(nr, nc) || newBoard[nr][nc] != 0) { can = false; break; }
}
if (can) {
m.clear();
for (Point p : norm) {
int nr = i + p.r, nc = j + p.c;
newBoard[nr][nc] = id;
m.addPoint(nr, nc);
}
placed = true;
}
}
}
if (!placed) {
m.removed = true;
m.clear();
}
}
board = newBoard;
}
static void printResult(int upto) {
int total = 0;
Set<String> seen = new HashSet<>();
for (int id1 = 1; id1 <= upto; id1++) {
Microbe m1 = microbes.get(id1);
if (m1 == null || m1.removed || m1.size() == 0) continue;
for (int id2 = id1 + 1; id2 <= upto; id2++) {
Microbe m2 = microbes.get(id2);
if (m2 == null || m2.removed || m2.size() == 0) continue;
if (isAdjacent(m1, m2)) {
String key = id1 + "," + id2;
if (!seen.contains(key)) {
seen.add(key);
total += m1.size() * m2.size();
}
}
}
}
System.out.println(total);
}
static boolean isAdjacent(Microbe m1, Microbe m2) {
for (Point p : m1.points) {
for (int d = 0; d < 4; d++) {
int nr = p.r + dr[d], nc = p.c + dc[d];
if (!OOB(nr, nc) && m2.contains(nr, nc)) return true;
}
}
return false;
}
static boolean OOB(int r, int c) {
return r < 0 || r >= N || c < 0 || c >= N;
}
}
// DFS (8방) — 같은 색 연결 성분 크기 구하기(폰 이동 규칙에서 사용)
static void dfs(int x, int y, int colorSign, boolean[][] vis, HashSet<Pair> acc){
if (OOB(x,y)) return;
int t = A[y][x]; // A[행][열] 접근
if (t == 0) return;
if ((t > 0) != (colorSign > 0)) return;
if (vis[y][x]) return; // vis[행][열] 접근
vis[y][x] = true;
Pair cur = new Pair(x,y); // (열, 행) 순서
acc.add(cur);
for (int d=0; d<8; d++){
dfs(x + dx[d], y + dy[d], colorSign, vis, acc);
}
}
// === 승진 처리: 승진한 쪽의 퀸 위치에서 상대 King들에게 거리제곱만큼 피해 ===
static void onPromote(boolean white){
Pair queen = (white ? wPos[N+1] : bPos[N+1]); // 폰 위치 = 퀸 위치로 취급
for (int i=1;i<=N;i++){
int hp = (white ? bHP[i] : wHP[i]);
if (hp > 0){
Pair enemy = (white ? bPos[i] : wPos[i]);
hp -= dist2(queen, enemy);
if (white) bHP[i] = hp; else wHP[i] = hp;
if (hp <= 0){
// 보드에서 제거
A[enemy.y][enemy.x] = 0; // A[행][열]
}
}
}
}
// === King 이동 시뮬레이션: dr 방향으로 '밀치기' 포함 ===
static boolean moveKing(int o, int dr, State S){
Pair p = (isWhite(o) ? S.wP[Math.abs(o)] : S.bP[Math.abs(o)]);
int x = p.x, y = p.y; // x=열, y=행
int nx = x + dx[dr], ny = y + dy[dr];
if (OOB(nx,ny)) return false;
// 제자리 비우기
S.B[y][x] = 0; // S.B[행][열]
x = nx; y = ny;
// 밀치기 루프
while (true){
int t = (OOB(x,y) ? 0 : S.B[y][x]);
// 보드 밖으로 밀린 경우
if (OOB(x,y)){
if (Math.abs(o) == N+1){ // Pawn이 밖으로 나가면: 직전 칸의 말을 제거
int px = x - dx[dr], py = y - dy[dr];
int pv = S.B[py][px];
setHPInState(S, pv, 0);
S.B[py][px] = o;
setPosInState(S, o, new Pair(px, py));
return true;
} else { // King이 밖으로 나가면: 본인 파괴
setHPInState(S, o, 0);
setPosInState(S, o, new Pair(x, y)); // 경계 밖 좌표 기록만(의미X)
return true;
}
}
if (t == 0){
S.B[y][x] = o;
setPosInState(S, o, new Pair(x, y));
return true;
}
// o가 King인지 Pawn인지에 따라
if (Math.abs(o) <= N){ // King
// 상대 Pawn(상대 N+1)이 있는 칸으로는 진입 불가
if (t == (N+1) * (isWhite(o)? -1 : 1)) return false;
if (Math.abs(t) <= N){ // King ↔ King 밀치기: 피해 후 교대 이동
int hp = getHPInState(S, t);
hp -= ( (o>0) == (t>0) ? CA : CB ); // 같은 색/다른 색 구분 피해
setHPInState(S, t, hp);
S.B[y][x] = o;
setPosInState(S, o, new Pair(x, y));
if (hp <= 0) return true;
// 다음 타자는 t가 되어, 한 칸 더 같은 방향으로 밀린다
o = t;
x += dx[dr]; y += dy[dr];
} else { // King이 Pawn을 밀치면: Pawn을 한 칸 더 민다
S.B[y][x] = o;
setPosInState(S, o, new Pair(x, y));
o = t; // 이제 대상(o)이 Pawn이 되어 계속 진행
x += dx[dr]; y += dy[dr];
}
} else { // o가 Pawn
if (Math.abs(t) == N+1){ // 같은 Pawn이면: 직전 칸의 말 제거하고 Pawn 정지
int px = x - dx[dr], py = y - dy[dr];
int pv = S.B[py][px];
setHPInState(S, pv, 0);
S.B[py][px] = o;
setPosInState(S, o, new Pair(px, py));
return true;
} else {
// Pawn이 King을 밀면: 그 King 제거하고 Pawn이 그 자리에 선다
setHPInState(S, t, 0);
S.B[y][x] = o;
setPosInState(S, o, new Pair(x, y));
return true;
}
}
}
}
// === State 기반 HP/좌표 헬퍼 ===
static int getHPInState(State S, int o){
if (o == 0) return 0;
int id = Math.abs(o);
if (id > N) return 0;
return (o>0) ? S.wH[id] : S.bH[id];
}
static void setHPInState(State S, int o, int v){
if (o == 0) return;
int id = Math.abs(o);
if (id > N) return;
if (o>0) S.wH[id] = v; else S.bH[id] = v;
}
static void setPosInState(State S, int o, Pair p){
int id = Math.abs(o);
if (o>0) S.wP[id] = p; else S.bP[id] = p;
}
// === King 한 번 이동(의사결정 포함) ===
static void stepKing(int o){
// 체력 0 이면 이동하지 않음
if (getHP(o) <= 0) return;
// 8방향 각각 시뮬(딥카피)
State baseline = new State();
baseline.B = copyBoard(A);
baseline.wP = copyPairs(wPos);
baseline.bP = copyPairs(bPos);
baseline.wH = copyArr(wHP);
baseline.bH = copyArr(bHP);
boolean[] can = new boolean[8];
State[] cand = new State[8];
for (int d=0; d<8; d++){
State S = baseline.deepCopy();
can[d] = moveKing(o, d, S);
cand[d] = S;
}
// 선호도 순대로 가장 좋은 방향 선택
int idx = Math.abs(o);
int bestDir = -1;
int bestDst = INF;
int bestX = INF;
int[] pref = (o>0) ? prefW[idx] : prefB[idx];
for (int k=0; k<8; k++){
int dr = pref[k];
if (!can[dr]) continue;
State S = cand[dr];
Pair pawn = (o>0) ? S.wP[N+1] : S.bP[N+1];
int dst = promoDist(o>0, pawn.y);
int x = pawn.x; // x좌표 (열)
if (dst < bestDst || (dst == bestDst && x < bestX)){
bestDst = dst; bestX = x; bestDir = dr;
}
}
if (bestDir == -1) return; // 어디도 못 움직임
// 최종 채택 상태로 커밋
State S = cand[bestDir];
A = S.B;
wPos = S.wP; bPos = S.bP;
wHP = S.wH; bHP = S.bH;
}
// === Pawn 한 번 이동 ===
static void stepPawn(int o){
Pair p = getPos(o);
int ox = p.x, oy = p.y; // x=열, y=행
// 같은 색 연결 성분 크기
boolean[][] vis = new boolean[H+1][W+1];
HashSet<Pair> comp = new HashSet<>();
dfs(ox, oy, o, vis, comp);
if (comp.size() > 4){
// 그룹이 크면: 승진에 가까워지도록 같은 색 내부에서 '스왑'
Pair best = null;
int bestD = INF;
int bestSum = INF;
for (Pair v : comp){
int dst = promoDist(o>0, v.y);
int sum = 0;
for (int i=1;i<=N+1;i++){
// 내 편 King(살아있는) + Pawn(N+1)까지 거리합
if (i == N+1 || getHP( (o>0? i : -i) ) > 0){
Pair q = getPos( o>0 ? i : -i );
sum += dist2(v, q);
}
}
if (dst < bestD || (dst == bestD && sum < bestSum)){
best = v; bestD = dst; bestSum = sum;
}
}
int k = A[best.y][best.x]; // A[행][열]
if (k != o){
// 위치 스왑
Pair kp = getPos(k);
int tmp = A[oy][ox];
A[oy][ox] = A[kp.y][kp.x];
A[kp.y][kp.x] = tmp;
setPos(o, new Pair(kp.x, kp.y));
setPos(k, new Pair(ox, oy));
}
} else {
// 그룹이 작으면: 비어있는 칸으로 1칸 이동(선호도: Pawn용=N+1)
int bestDir = -1;
int bestScore = INF;
int[] pref = (o>0) ? prefW[N+1] : prefB[N+1];
for (int k=0; k<8; k++){
int dr = pref[k];
int nx = ox + dx[dr], ny = oy + dy[dr];
if (OOB(nx,ny) || A[ny][nx] != 0) continue;
// 자신의 King들과의 거리합이 최소가 되는 방향
int sum = 0;
for (int i=1;i<=N;i++){
if (getHP( (o>0? i : -i) ) > 0){
Pair q = getPos( o>0 ? i : -i );
sum += dist2(new Pair(nx,ny), q);
}
}
if (sum < bestScore){
bestScore = sum; bestDir = dr;
}
}
if (bestDir != -1){
A[oy][ox] = 0;
int nx = ox + dx[bestDir], ny = oy + dy[bestDir];
A[ny][nx] = o;
setPos(o, new Pair(nx,ny));
}
}
}
// === 한 기물(o) 차례 처리: King/Pawn 구분 ===
// 반환값: true → 아직 승진 전, false → 방금 승진(또는 이미 승진 상태)
static boolean stepOne(int o){
if (Math.abs(o) <= N){
// King: 체력 0 이하면 스킵
if (getHP(o) > 0) stepKing(o);
} else {
// Pawn
stepPawn(o);
}
// 승진 여부 체크
Pair myPawn = getPos( isWhite(o) ? (N+1) : -(N+1) );
int d = promoDist(isWhite(o), myPawn.y);
return d > 0;
}
// === 출력 ===
static void printBoard(){
StringBuilder sb = new StringBuilder();
for (int i=1;i<=H;i++){
for (int j=1;j<=W;j++){
int v = A[i][j]; // A[행][열]
if (v == 0){
sb.append('.');
} else if (v > 0 && v <= N){
sb.append('K').append(v);
} else if (v < 0 && -v <= N){
sb.append('k').append(-v);
} else if (v == (N+1)){
sb.append( (i==1) ? 'Q' : 'P' );
} else if (v == -(N+1)){
sb.append( (i==H) ? 'q' : 'p' );
}
if (j < W) sb.append(' ');
}
sb.append('\n');
}
System.out.print(sb);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 입력
H = sc.nextInt();
W = sc.nextInt();
N = sc.nextInt();
K = sc.nextInt();
CA = sc.nextInt();
CB = sc.nextInt();
int totalPieces = 2*N + 2;
// 보드/상태 초기화
A = new int[H+1][W+1];
wPos = new Pair[N+2];
bPos = new Pair[N+2];
for (int i=1;i<=N+1;i++){
wPos[i] = new Pair(0,0);
bPos[i] = new Pair(0,0);
}
wHP = new int[N+1];
bHP = new int[N+1];
order = new int[totalPieces];
// 기물 입력
for (int i=0;i<totalPieces;i++){
String name = sc.next();
int r = sc.nextInt(); // 행
int c = sc.nextInt(); // 열
int id = readPieceCode(name); // +i/-i, +-(N+1)
order[i] = id;
A[r][c] = id; // A[행][열]
if (id > 0){
int idx = Math.abs(id);
wPos[idx] = new Pair(c, r); // Pair(열, 행)
} else {
int idx = Math.abs(id);
bPos[idx] = new Pair(c, r); // Pair(열, 행)
}
}
// 방향 선호 (N+1줄: King1..N + Pawn)
prefW = new int[N+2][8];
prefB = new int[N+2][8];
for (int i=1;i<=N+1;i++){
String s = sc.next(); // 길이 8, 각 글자 '0'..'7'
for (int k=0;k<8;k++) prefW[i][k] = s.charAt(k) - '0';
}
for (int i=1;i<=N+1;i++){
String s = sc.next();
for (int k=0;k<8;k++) prefB[i][k] = s.charAt(k) - '0';
}
// HP
for (int i=1;i<=N;i++) wHP[i] = sc.nextInt();
for (int i=1;i<=N;i++) bHP[i] = sc.nextInt();
// 시뮬레이션: 최대 K턴, 매 턴 order 순서대로
outer:
for (int t=0; t<K; t++){
for (int o : order){
boolean notPromoted = stepOne(o);
if (!notPromoted){
// 방금 승진 → 퀸 딜 후 즉시 종료
onPromote(o > 0);
break outer;
}
}
}
printBoard();
}
}
일일 요리 집단 활동 루프 (T일 반복)
├── 아침 활동 (breakfast)
│ ├── 전체 요리사 신앙심 증가
│ │ ├── 모든 칸 (r,c)에 대해
│ │ ├── B[r][c] += 1 (신앙심 1씩 증가)
│ │ └── 하루 시작의 의욕 상승 표현
│ │
│ └── 기본 에너지 충전 완료
│
├── 점심 활동 (lunch) - 그룹 형성 및 신앙심 재분배
│ ├── 같은 음식 그룹 탐색 (BFS/DFS)
│ │ ├── 전체 격자 스캔 (행→열 순서)
│ │ │ ├── 미방문 칸에서 시작
│ │ │ ├── 음식 없는 칸(F[r][c]=0) 스킵
│ │ │ └── 같은 음식 타입끼리 4방향 연결성 탐색
│ │ │
│ │ ├── 그룹별 리더 선정
│ │ │ ├── 그룹 내 최대 신앙심(B값) 탐색
│ │ │ ├── 최대값이 여러개면 첫 번째 발견된 좌표
│ │ │ └── 리더 좌표 [lr, lc] 결정
│ │ │
│ │ └── 그룹 정보 수집
│ │ ├── 음식 타입 (F값)
│ │ ├── 그룹 크기 (연결된 칸 수)
│ │ ├── 리더 위치
│ │ └── 구성원 좌표 집합
│ │
│ ├── 그룹 내 신앙심 재분배
│ │ ├── 각 그룹별 독립적 처리
│ │ ├── 리더 강화: B[leader] += (그룹크기 - 1)
│ │ ├── 구성원 약화: B[member] -= 1 (리더 제외)
│ │ └── 리더 중심의 위계질서 확립
│ │
│ └── 저녁 활동을 위한 그룹 정보 전달
│
├── 저녁 활동 (dinner) - 음식 전파 및 정복
│ ├── 그룹 우선순위 결정
│ │ ├── 1순위: 음식타입 자릿수 적은 순 (길이 우선)
│ │ ├── 2순위: 리더 신앙심 높은 순 (B값 내림차순)
│ │ ├── 3순위: 리더 행 좌표 작은 순 (lr 오름차순)
│ │ └── 4순위: 리더 열 좌표 작은 순 (lc 오름차순)
│ │
│ ├── 우선순위 순서대로 전파 실행
│ │ ├── 각 그룹의 리더에서 시작
│ │ ├── 전파 방향 결정: dir = B[leader] % 4
│ │ │ ├── 0: 위(-1,0), 1: 아래(1,0)
│ │ │ ├── 2: 왼쪽(0,-1), 3: 오른쪽(0,1)
│ │ │ └── 신앙심에 따른 운명적 방향
│ │ │
│ │ ├── 전파 에너지 계산: earnest = B[leader] - 1
│ │ ├── 리더 신앙심 초기화: B[leader] = 1
│ │ │
│ │ └── 직선 전파 진행
│ │ ├── 방향으로 한 칸씩 이동하며 진행
│ │ ├── 경계 벗어나거나 에너지 소진시 중단
│ │ │
│ │ ├── 각 칸별 전파 규칙
│ │ │ ├── 같은 음식 타입: 스킵 (전파 안함)
│ │ │ ├── 이미 전파된 칸: 스킵 (중복 방지)
│ │ │ │
│ │ │ ├── 강한 전파 (earnest > 기존 신앙심)
│ │ │ │ ├── F[nr][nc] = 리더 음식타입 (완전 정복)
│ │ │ │ ├── B[nr][nc] = 기존값 + 1
│ │ │ │ └── earnest -= (기존값 + 1)
│ │ │ │
│ │ │ └── 약한 전파 (earnest ≤ 기존 신앙심)
│ │ │ ├── F[nr][nc] = mixFood(기존, 리더) (융합)
│ │ │ ├── B[nr][nc] = 기존값 + earnest
│ │ │ └── earnest = 0 (에너지 소진)
│ │ │
│ │ └── 전파 완료 후 다음 그룹으로
│ │
│ └── 모든 그룹 전파 완료
│
├── 결과 집계 및 출력
│ ├── 음식 타입별 신앙심 총합 계산
│ │ ├── 전체 격자 스캔
│ │ ├── 각 음식 타입별로 B값 누적
│ │ └── Map<음식타입, 총신앙심> 생성
│ │
│ ├── 정해진 순서로 출력
│ │ ├── 출력 순서: [123, 12, 13, 23, 3, 2, 1]
│ │ ├── 해당 타입 존재시: 총합 출력
│ │ ├── 해당 타입 없으면: 0 출력
│ │ └── 공백으로 구분하여 한 줄 출력
│ │
│ └── 하루 활동 완료
│
└── T일 완료 후 시뮬레이션 종료
그룹 탐색 알고리즘 (BFS):
├── 연결성 탐색
│ ├── 시작점: 미방문이고 음식이 있는 칸
│ ├── 확장 조건: 4방향 인접 + 같은 음식 타입
│ ├── 탐색 결과: 연결된 모든 좌표의 집합
│ └── 그룹 크기: 연결된 칸의 개수
│
├── 리더 선정 규칙
│ ├── 기준: 그룹 내 최대 신앙심 (B값)
│ ├── 동점 처리: 탐색 순서상 먼저 발견된 좌표
│ └── 리더 역할: 그룹 대표 + 전파 시작점
│
└── 신앙심 재분배
├── 리더 보상: +그룹크기-1 (리더십 보상)
├── 구성원 비용: -1 (리더에게 힘 기부)
└── 집단 내 위계질서 강화
mixFood 알고리즘:
├── 입력: 두 음식 타입 (정수)
├── 처리 과정
│ ├── 각 숫자를 문자열로 분해
│ ├── 모든 자릿수를 Set에 추가 (중복 제거)
│ ├── TreeSet 자동 정렬 (오름차순)
│ └── 정렬된 숫자들을 연결하여 새 정수 생성
│
├── 예시
│ ├── mixFood(12, 23) = 123 (1,2,3 → "123")
│ ├── mixFood(1, 2) = 12 (1,2 → "12")
│ └── mixFood(13, 23) = 123 (1,3,2,3 → 1,2,3 → "123")
│
└── 의미: 다른 음식 문화의 창조적 융합
그룹 정렬 규칙 (Group.compareTo):
├── 1순위: 음식타입 자릿수 (length 오름차순)
│ ├── 1 < 12 < 123 (단순한 음식이 먼저)
│ └── 전통적이고 순수한 음식의 우선권
│
├── 2순위: 리더 신앙심 (B값 내림차순)
│ ├── 강한 리더가 먼저 행동
│ └── 카리스마와 영향력 기반 순서
│
├── 3순위: 행 좌표 (lr 오름차순)
│ └── 북쪽 그룹 우선
│
└── 4순위: 열 좌표 (lc 오름차순)
└── 서쪽 그룹 우선
직선 전파 알고리즘:
├── 초기 설정
│ ├── 방향: dir = B[leader] % 4 (신앙심 기반 운명)
│ ├── 에너지: earnest = B[leader] - 1
│ └── 리더 초기화: B[leader] = 1
│
├── 진행 규칙
│ ├── 경계 조건: 격자 밖이면 중단
│ ├── 에너지 조건: earnest ≤ 0이면 중단
│ ├── 같은 음식: 스킵 (동족 보호)
│ └── 이미 전파된 칸: 스킵 (중복 방지)
│
├── 정복 vs 융합
│ ├── 강한 전파 (earnest > 기존 신앙심)
│ │ ├── 완전 정복: 음식 타입 덮어쓰기
│ │ ├── 신앙심 증가: +1
│ │ └── 에너지 소모: -(기존값+1)
│ │
│ └── 약한 전파 (earnest ≤ 기존 신앙심)
│ ├── 문화 융합: mixFood로 새 음식 생성
│ ├── 신앙심 흡수: +earnest
│ └── 에너지 소진: earnest = 0
│
└── 전파 완료 조건
├── 에너지 소진 (earnest = 0)
├── 경계 도달
└── 더 이상 진행 불가
집단 행동 모델:
├── 아침: 개인의 의욕 증진 (전체 +1)
├── 점심: 집단 형성 및 리더십 확립
├── 저녁: 집단간 경쟁 및 영토 확장
└── 순환: 매일 반복되는 사회 역학
음식 문화 확산:
├── 순수 전파: 강한 집단의 문화 정복
├── 융합 전파: 약한 상황에서 문화 혼합
├── 방향성: 리더 신앙심에 따른 운명적 방향
└── 우선순위: 전통성과 순수성 중시
import java.io.*;
import java.util.*;
//import practice.Point;
public class Main {
// 상태 변수
static int N, T;
// 방향 변수 : 0, 1, 2, 3 : 위, 아래, 왼쪽, 오른쪽
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int[][] F;
static int[][] B;
static class Point implements Comparable<Point> {
int r, c;
Point(int r, int c) { this.r = r; this.c = c; }
@Override
public int compareTo(Point o) {
if (r != o.r) return r - o.r;
return c - o.c;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Point)) return false;
Point p = (Point) o;
return r == p.r && c == p.c;
}
@Override
public int hashCode() {
return Objects.hash(r, c);
}
}
static class Group implements Comparable<Group> {
int groupType; // F type
int groupTypeLen;
int lr, lc;
Set<Point> points;
Group(int groupType, int lr, int lc, Set<Point> points) {
this.groupType = groupType;
this.groupTypeLen = Integer.toString(groupType).length();
this.lr = lr;
this.lc = lc;
this.points = points;
}
// @Override
// public int compareTo(Group o) {
// if (this.groupTypeLen != o.groupTypeLen) {
// return this.groupTypeLen - o.groupTypeLen;
// }
// if (this.lr != o.lr) {
// return this.lr - o.lr;
// }
// return this.lc - o.lc;
// }
@Override
public int compareTo(Group o) {
if (this.groupTypeLen != o.groupTypeLen) {
return this.groupTypeLen - o.groupTypeLen;
}
// ⭐ 신앙심 비교 추가 (내림차순)
if (B[this.lr][this.lc] != B[o.lr][o.lc]) {
return Integer.compare(B[o.lr][o.lc], B[this.lr][this.lc]);
}
if (this.lr != o.lr) {
return this.lr - o.lr;
}
return this.lc - o.lc;
}
}
// 유틸
static int convert(char c) {
if (c == 'T') return 1; // 민트
if (c == 'C') return 2; // 초코
if (c == 'M') return 3; // 우유
return 0;
}
static boolean OOB(int r, int c) {
return (r < 0 || c < 0 || r >= N || c >= 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());
F = new int[N][N];
B = new int[N][N];
T = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String str = st.nextToken();
for (int j = 0; j < N; j++) {
F[i][j] = convert(str.charAt(j));
}
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
B[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < T; i++) {
int step = i+1;
breakfast();
lunch();
printResult();
System.out.println("");
}
}
static void breakfast() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
B[i][j]++;
}
}
}
static Set<Point> dfs(int r, int c, boolean[][] visited, List<int[]> leaders) {
Set<Point> s = new TreeSet<>();
int food = F[r][c];
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {r, c});
s.add(new Point(r, c));
visited[r][c] = true;
int maxB = B[r][c];
while(!q.isEmpty()) {
int[] tq = q.poll();
int cr = tq[0];
int cc = tq[1];
for (int i = 0 ; i < 4; i++) {
int nr = cr + dr[i];
int nc = cc + dc[i];
if (OOB(nr, nc) || visited[nr][nc]) continue;
if (F[nr][nc] == food) {
visited[nr][nc] = true;
q.add(new int[] {nr, nc});
s.add(new Point(nr, nc));
if (B[nr][nc] > maxB) maxB = B[nr][nc];
}
}
}
int[] ld = chooseLeader(s, maxB);
leaders.add(ld);
// leader Value
return s;
}
static int[] chooseLeader(Set<Point> s, int maxB) {
for (Point p : s) {
if (B[p.r][p.c] == maxB) return new int[] {p.r, p.c};
}
return new int[] {-1, -1};
}
static void lunch() {
boolean[][] visited = new boolean[N][N];
List<Set<Point>> groups = new ArrayList<>();
List<int[]> leaders = new ArrayList<>();
List<Integer> groupType = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// ====== 수정 시작 =====
// 음식 없음: 그룹 스킵 (버그픽스 1)
if(F[i][j]==0){
visited[i][j]=true;
continue;
}
// ====== 수정 =====
if (!visited[i][j]) {
groupType.add(F[i][j]);
groups.add(dfs(i, j, visited, leaders));
}
}
}
for (int i = 0; i < groups.size(); i++) { // group size가 하나일 때
Set<Point> s = groups.get(i);
int[] leader = leaders.get(i);
int groupSize = s.size();
for (Point p : s) {
if (p.r == leader[0] && p.c == leader[1])
B[p.r][p.c] += (groupSize-1);
else B[p.r][p.c]--;
}
}
dinner(groups, groupType, leaders);
}
static int mixFood(int a, int b) {
Set<Character> set = new TreeSet<>(); // 중복 제거 + 자동 정렬
for (char c : Integer.toString(a).toCharArray()) {
set.add(c);
}
for (char c : Integer.toString(b).toCharArray()) {
set.add(c);
}
StringBuilder sb = new StringBuilder();
for (char c : set) {
sb.append(c);
}
return Integer.parseInt(sb.toString());
}
static void dinner(List<Set<Point>> groups, List<Integer> groupType, List<int[]> leaders) {
List<Group> groupList = new ArrayList<>();
for (int i = 0; i < groups.size(); i++) {
int gt = groupType.get(i);
int lr = leaders.get(i)[0];
int lc = leaders.get(i)[1];
Set<Point> gp = groups.get(i);
groupList.add(new Group(gt, lr, lc, gp));
}
Collections.sort(groupList);
boolean[][] isSpreaded = new boolean[N][N];
for (int i = 0; i < groupList.size(); i++) {
Group g = groupList.get(i);
int lr = g.lr;
int lc = g.lc;
if (isSpreaded[lr][lc]) continue;
int earnest = B[lr][lc] - 1;
int dir = B[lr][lc] % 4;
int foodType = g.groupType;
B[lr][lc] = 1;
int nr = lr;
int nc = lc;
while(true) {
nr += dr[dir];
nc += dc[dir];
if (OOB(nr, nc) || earnest <= 0) break;
int cf = F[nr][nc];
// 이거 위치
if(cf==foodType){continue;}
int prevB = B[nr][nc];
boolean isStrong = (earnest > prevB) ? true : false;
if (isStrong) {
F[nr][nc] = foodType;
B[nr][nc] = prevB + 1;
earnest -= (prevB + 1);
}
else {
F[nr][nc] = mixFood(cf, foodType);
B[nr][nc] = prevB + earnest;
earnest = 0;
}
isSpreaded[nr][nc] = true;
if (earnest <= 0) break;
}
}
}
static void printResult() {
// T : 민트 => 1
// C : 초코 => 2
// M : 우유 => 3
// 123. 12. 13. 23. 3. 2. 1
int[] order = {123, 12, 13, 23, 3, 2, 1};
Map<Integer, Integer> hm = new HashMap<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int f = F[i][j];
hm.put(f, hm.getOrDefault(f, 0) + B[i][j]);
}
}
for (int key : order) {
if (hm.containsKey(key) )
System.out.print(hm.get(key) + " ");
else System.out.print(0 + " ");
}
}
static void printBoard(String name, int[][] board) {
System.out.println("--- " + name + " ---");
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
메두사 vs 전사들 시뮬레이션
├── 초기 설정
│ ├── 지형 정보 입력
│ │ ├── N×N 격자 (도로=0, 장애물=1)
│ │ ├── 메두사 시작 위치
│ │ ├── 공원(목적지) 위치
│ │ └── M명 전사들의 초기 위치
│ │
│ └── 최단거리 사전 계산 (BFS)
│ ├── 공원에서 모든 칸까지의 최단거리 계산
│ ├── 도로(0)만 통과 가능
│ ├── dist[r][c] = 공원까지의 최단거리
│ └── 도달 불가능한 칸은 -1로 설정
│
├── 메인 게임 루프 (메두사가 공원 도달 또는 갇힐 때까지)
│ ├── 1단계: 메두사 이동
│ │ ├── 4방향 중 공원으로 가는 최단 경로 선택
│ │ │ ├── 이동 조건 확인
│ │ │ │ ├── 경계 내부 (0 ≤ r,c < N)
│ │ │ │ ├── 도로 위 (town[r][c] = 0)
│ │ │ │ └── 공원까지 거리가 단축됨
│ │ │ ├── 최단거리 방향 선택 (상→하→좌→우 우선순위)
│ │ │ └── 메두사 위치 업데이트
│ │ │
│ │ ├── 이동 결과 확인
│ │ │ ├── 공원 도달시: 0 출력 후 게임 종료
│ │ │ ├── 갈 곳 없음: -1 출력 후 게임 종료
│ │ │ └── 정상 이동: 다음 단계 진행
│ │ │
│ │ └── 같은 칸 전사 즉시 처치
│ │ ├── 메두사 이동 후 위치의 전사들 스캔
│ │ └── 해당 전사들의 isAlive = false
│ │
│ ├── 2단계: 메두사 시야 공격
│ │ ├── 4방향 시야 시뮬레이션
│ │ │ ├── 각 방향별 독립적 시야 계산
│ │ │ ├── 3갈래 확산 (좌대각, 직선, 우대각)
│ │ │ │ ├── 상: [(-1,-1), (-1,0), (-1,1)]
│ │ │ │ ├── 하: [(1,-1), (1,0), (1,1)]
│ │ │ │ ├── 좌: [(-1,-1), (0,-1), (1,-1)]
│ │ │ │ └── 우: [(-1,1), (0,1), (1,1)]
│ │ │ │
│ │ │ ├── BFS 확산 및 가려짐 처리
│ │ │ │ ├── 메두사 위치에서 3갈래로 BFS 확산
│ │ │ │ ├── 전사 발견시 해당 갈래에서 뒤쪽 차단
│ │ │ │ ├── 가려짐 영역 계산 (전사 뒤 그림자)
│ │ │ │ └── 최종 시야 영역 결정
│ │ │ │
│ │ │ └── 시야 내 전사 수 계산
│ │ │
│ │ ├── 최적 방향 선택 (가장 많은 전사 보이는 방향)
│ │ └── 선택된 방향으로 석화 공격 실행
│ │ ├── 시야 내 전사들 석화 (isAttacked = true)
│ │ ├── 보드에 시야 영역 표시 (board[r][c] = -1)
│ │ └── 석화된 전사 수 반환
│ │
│ ├── 3단계: 전사들 이동
│ │ ├── 살아있고 석화되지 않은 전사들만 이동
│ │ ├── 각 전사별 2번 이동 기회
│ │ │ ├── 1차 이동 (상→하→좌→우 우선순위)
│ │ │ │ ├── 메두사와의 거리가 줄어드는 방향만 고려
│ │ │ │ ├── 시야 영역(board[r][c] = -1) 진입 금지
│ │ │ │ ├── 경계 확인 및 이동 가능성 검사
│ │ │ │ └── 조건 만족시 이동 실행
│ │ │ │
│ │ │ ├── 메두사 도달 확인
│ │ │ │ └── 메두사와 같은 칸이면 추가 이동 중단
│ │ │ │
│ │ │ └── 2차 이동 (좌→우→상→하 우선순위)
│ │ │ ├── 동일한 조건으로 거리 단축 이동
│ │ │ └── 총 이동 거리 누적
│ │ │
│ │ └── 전체 전사 이동 거리 합계 반환
│ │
│ ├── 4단계: 전사들 공격
│ │ ├── 메두사와 같은 칸에 있는 전사들 확인
│ │ ├── 해당 전사들이 메두사 공격 (1:1 교환)
│ │ ├── 공격한 전사들 제거 (isAlive = false)
│ │ └── 공격한 전사 수 반환
│ │
│ ├── 5단계: 결과 출력 및 정리
│ │ ├── 이번 턴 결과 출력
│ │ │ ├── 전사 총 이동거리
│ │ │ ├── 석화된 전사 수
│ │ │ └── 메두사를 공격한 전사 수
│ │ │
│ │ └── 석화 해제 (다음 턴 준비)
│ │ ├── 모든 전사의 isAttacked = false
│ │ └── 석화는 1턴만 지속
│ │
│ └── 다음 턴으로 진행 또는 게임 종료
│
└── 게임 종료 조건
├── 메두사 공원 도달: 0 출력
├── 메두사 갇힘: -1 출력
└── 모든 전사 제거: 메두사 승리 계속 진행
시야 계산 알고리즘:
├── 3갈래 BFS 확산
│ ├── 메두사 위치에서 방향별 3갈래로 동시 확산
│ ├── 각 갈래: 좌대각, 직선, 우대각
│ ├── BFS로 점진적 확산하며 시야 영역 구성
│ └── 격자 경계까지 확산
│
├── 전사 기반 가려짐 처리
│ ├── 전사 발견시 해당 좌표를 차단점으로 등록
│ ├── 차단점 분류
│ │ ├── type 0: 좌대각 갈래의 전사
│ │ ├── type 1: 직선 갈래의 전사
│ │ └── type 2: 우대각 갈래의 전사
│ ├── 갈래별 그림자 처리
│ │ ├── 좌갈래(type 0): 좌+직선 방향만 차단
│ │ ├── 직선갈래(type 1): 직선 방향만 차단
│ │ └── 우갈래(type 2): 직선+우 방향만 차단
│ └── 재귀적 그림자 확산으로 가려진 영역 제거
│
└── 최종 시야 결과
├── vis[r][c] = 1: 보이는 영역
├── vis[r][c] = 0: 보이지 않는 영역
└── 시야 내 전사 수 합계
전사 이동 알고리즘:
├── 이동 자격 확인
│ ├── isAlive = true (살아있음)
│ └── isAttacked = false (석화되지 않음)
│
├── 거리 기반 이동 결정
│ ├── 현재 메두사와의 맨해튼 거리 계산
│ ├── 4방향 중 거리가 줄어드는 방향만 고려
│ ├── 동일 거리 단축시 우선순위 적용
│ │ ├── 1차: 상(0)→하(1)→좌(2)→우(3)
│ │ └── 2차: 좌(2)→우(3)→상(0)→하(1)
│ └── 시야 영역 진입 금지 (board[r][c] = -1)
│
├── 2단계 이동 실행
│ ├── 1차 이동 후 메두사 도달시 2차 이동 중단
│ ├── 각 이동마다 거리 단축 조건 재확인
│ └── 총 이동 거리 누적
│
└── 이동 결과
├── 전사 위치 업데이트
└── 총 이동 거리 반환
메두사 이동 알고리즘:
├── 사전 계산된 최단거리 활용
│ ├── BFS로 공원에서 모든 칸까지 거리 계산
│ ├── 도로(0)만 통과 가능
│ └── dist[r][c] = 공원까지의 최단거리
│
├── 최적 방향 선택
│ ├── 4방향 중 dist 값이 가장 작은 방향
│ ├── 이동 조건: 경계 내 + 도로 위 + 도달 가능
│ └── 동일 거리시 상→하→좌→우 우선순위
│
├── 이동 실행
│ ├── 메두사 위치 업데이트
│ ├── 같은 칸 전사 즉시 제거
│ └── 도달 결과 확인
│
└── 종료 조건 확인
├── 공원 도달: 0 반환 (게임 승리)
├── 갇힘: -1 반환 (이동 불가)
└── 정상: 1 반환 (게임 계속)
메두사 vs 전사들:
├── 메두사 장점
│ ├── 강력한 원거리 공격 (시야)
│ ├── 명확한 승리 조건 (공원 도달)
│ └── 접촉시 전사 즉시 처치
│
├── 전사들 장점
│ ├── 수적 우위 (M명)
│ ├── 기동성 (2번 이동)
│ └── 메두사 접촉시 1:1 교환
│
└── 균형 요소
├── 시야 가려짐 (전사들의 방어 수단)
├── 석화 1턴 지속 (임시 무력화)
└── 지형 제약 (도로만 이동 가능)
핵심 전략:
├── 메두사 전략
│ ├── 최단 경로 유지
│ ├── 시야 최적화 (최대 전사 석화)
│ └── 전사 접근 차단
│
├── 전사 전략
│ ├── 협동 포위 (다방향 접근)
│ ├── 그림자 활용 (시야 차단)
│ └── 희생 전술 (1:1 교환)
│
└── 지형 활용
├── 좁은 통로에서의 유리함
├── 시야 차단 지형 활용
└── 최적 경로 예측 및 차단
import java.io.*;
import java.util.*;
// 맨핻튼 거리 : 그냥 가로 빼기 세로 뺴기
public class Main {
// 게임 설정
static int N, M;
// 방향 : 상, 하, 좌,
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int[] medusa = new int[2]; // 이거 포인트로 갈 수도 있음.
static int[] park = new int[2];;
static int[][] town;
static int[][] dist ;
static class Warrior {
int r, c;
boolean isAlive;
boolean isAttacked;
Warrior(int r, int c) {
this.r = r;
this.c = c;
this.isAlive = true;
this.isAttacked = false;
}
}
static List<Warrior> warriors = new LinkedList<>(); // 얘네 삭제 조심
// 유틸
static boolean OOB(int r, int c) {
return (r < 0|| c < 0 || r >= N || c >= N);
}
static boolean isRoad(int r, int c) {
return town[r][c] == 0;
}
// === 헬퍼 ===
// 방향별 3갈래(좌,직선,우)
static final int[][][] VISION = {
{ {-1,-1}, {-1,0}, {-1,1} }, // 상
{ { 1,-1}, { 1,0}, { 1,1} }, // 하
{ {-1,-1}, { 0,-1}, { 1,-1} },// 좌
{ {-1, 1}, { 0, 1}, { 1, 1} } // 우
};
// 현재 살아있는 전사 수를 칸별로 누적한 맵
static int[][] buildWarriorCountGrid() {
int[][] cnt = new int[N][N];
for (Warrior w : warriors) {
if (!w.isAlive) continue;
cnt[w.r][w.c]++;
}
return cnt;
}
static boolean inRange(int r, int c) {
return 0 <= r && r < N && 0 <= c && c < N;
}
static class VisionResult {
int[][] vis; // 1=보임, 0=안보임
int seen; // 시야에 남은 전사 수
VisionResult(int[][] vis, int seen){ this.vis = vis; this.seen = seen; }
}
static VisionResult buildVision(int dir) {
int mr = medusa[0], mc = medusa[1];
int[][] vis = new int[N][N];
int[][] wcnt = buildWarriorCountGrid();
Deque<int[]> q = new ArrayDeque<>();
Deque<int[]> occ = new ArrayDeque<>(); // (r,c,type) type: 0=좌, 1=직선, 2=우
int[][] d3 = VISION[dir];
// 3갈래 BFS 확장
q.add(new int[]{mr, mc});
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
for (int i = 0; i < 3; i++) {
int nr = r + d3[i][0], nc = c + d3[i][1];
if (!inRange(nr, nc) || vis[nr][nc] == 1) continue;
if (wcnt[nr][nc] > 0) {
int type;
if (nr == mr || nc == mc) type = 1; // 같은 행/열이면 직선
else {
// 기준(좌= d3[0])과 같은 부호면 좌, 아니면 우
boolean sameSign = (nr - mr) * d3[0][0] > 0 && (nc - mc) * d3[0][1] > 0;
type = sameSign ? 0 : 2;
}
occ.add(new int[]{nr, nc, type});
}
vis[nr][nc] = 1;
q.add(new int[]{nr, nc});
}
}
// 가려짐 처리: 각 갈래에서 전사 뒤쪽은 보이지 않도록 0으로 지움
while (!occ.isEmpty()) {
int[] cur = occ.poll();
int r = cur[0], c = cur[1], t = cur[2];
for (int i = 0; i < 3; i++) {
if (t == 1 && i != 1) continue; // 직선은 i=1만
if (t == 0 && i == 2) continue; // 좌는 좌/직선만
if (t == 2 && i == 0) continue; // 우는 직선/우만
int nr = r + d3[i][0], nc = c + d3[i][1];
if (!inRange(nr, nc) || vis[nr][nc] == 0) continue;
vis[nr][nc] = 0;
occ.add(new int[]{nr, nc, t});
}
}
// 최종 시야에 남은 전사 수 합산
int seen = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (vis[i][j] == 1) seen += wcnt[i][j];
return new VisionResult(vis, seen);
}
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());
town = new int[N][N];
st = new StringTokenizer(br.readLine());
medusa[0] = Integer.parseInt(st.nextToken());
medusa[1] = Integer.parseInt(st.nextToken());
park[0] = Integer.parseInt(st.nextToken());
park[1] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
warriors.add(new Warrior(r, c));
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
// 도로 : 0, 도로 아닌 곳 : 1
town[i][j] = Integer.parseInt(st.nextToken());
}
}
// (0) 최단거리 미리 계산
calculateMinDist();
while(true) { // 메두사가 공원 도달할 때까지 턴 진행
// (1) 메두사 이동
int afterMove = moveMedusa();
if (afterMove == 0) { // 공원 도착
System.out.println(afterMove);
break;
}
if (afterMove == -1) { // 갈 곳 없음
System.out.println(afterMove);
break;
}
// 여기서현재 메두사의 위치, 시선, 병사 다 저장.
// 0 : 빈 곳
// 1 : 메두사
// -1 : 시선
int[][] board = new int[N][N];
board[medusa[0]][medusa[1]] = 1;
// 전사 처리
for (Warrior w : warriors) {
if (!w.isAlive) continue;
board[w.r][w.c] = 2;
}
// (2) 메두사의 공격(시선)
int rockCnt = stairing(board);
// (3) 전사의 이동
int totalDist = moveWarrior(board);
// (4) 전사의 공격
int attackCnt = attack();
// (5) 결과 출력
printResult(totalDist, rockCnt, attackCnt);
// 돌이 된 병사들 풀어주기
releaseWarrior();
}
}
// 0. 메두사, 공원 최단 거리 계산 : 다익스트라,그래프?탐색
static void calculateMinDist() {
dist = new int[N][N];
for (int i = 0; i < N; i++) Arrays.fill(dist[i], -1);
Deque<int[]> q = new ArrayDeque<>();
int pr = park[0], pc = park[1];
// 공원이 도로(0)인 경우에만 시작 가능. 아니라면 전체 -1 유지.
if (!isRoad(pr, pc)) return;
dist[pr][pc] = 0;
q.add(new int[]{pr, pc});
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (OOB(nr, nc)) continue;
if (!isRoad(nr, nc)) continue; // 도로(0)만 이동 가능
if (dist[nr][nc] != -1) continue; // 이미 방문
dist[nr][nc] = dist[r][c] + 1;
q.add(new int[]{nr, nc});
}
}
}
static void killWarrior(int mr, int mc) {
for (Warrior w : warriors) {
if (!w.isAlive) continue;
if (w.r == mr && w.c == mc) w.isAlive = false;
}
}
// 1. 메두사 이동
static int moveMedusa() {
// 1. 메두사 이동
// 도로 따라 한 칸 이동
// 1. 공원까지 최단 경로
// 2. 상, 하, 좌, 우
// if 메 -> 집 경로 없음 () ====> -1 출력하고 종료
// 3. 이동 후
// if 메두사 공원 도착? 0 출력하고 프로그램 종료 --> 이거 앞에 가도 될 것 같은데
// if 전사 있음 : 전사가 메두사 공격 받고 죽음(이때 죽는 위치 조심)
// dist[r][c] = 공원(park)에서 (r,c)까지의 최단거리 (도로=0만 통과). 도달 불가 = -1.
// medusa[][] 위치 업데이트
int cmr = medusa[0];
int cmc = medusa[1];
int minDist = Integer.MAX_VALUE;
int dir = -1;
for (int i = 0; i < 4; i++) {
int nmr = cmr + dr[i];
int nmc = cmc + dc[i];
// if (OOB(nmr, nmc)) continue;
if (OOB(nmr, nmc) || !isRoad(nmr, nmc)) continue; // <- 추가하면 의도 명확
if (dist[nmr][nmc] == -1) continue;
if (dist[nmr][nmc] < minDist) {
minDist = dist[nmr][nmc];
dir = i;
}
}
if (dir == -1) return -1;
cmr += dr[dir];
cmc += dc[dir];
medusa[0] = cmr;
medusa[1] = cmc;
if (medusa[0] == park[0] && medusa[1] == park[1]) return 0;
killWarrior(medusa[0], medusa[1]);
return 1;
}
// 보드에 시야만 -1로 칠하고, 보이는 전사 수만 반환 (전사 상태 변경 없음)
static int mockSimulate(int dir, int[][] board) {
VisionResult vr = buildVision(dir);
int[][] vis = vr.vis;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (vis[r][c] == 1) board[r][c] = -1; // 금지 칸
}
}
return vr.seen;
}
// 실제 적용: 시야 칠하고, 보이는 전사를 이번 턴 석화(isAttacked=true), 석화 수 반환
static int simulate(int dir, int[][] board) {
VisionResult vr = buildVision(dir);
int[][] vis = vr.vis;
// 보드 칠 + 전사 석화
int turned = 0;
for (Warrior w : warriors) {
if (!w.isAlive) continue;
if (vis[w.r][w.c] == 1) {
if (!w.isAttacked) w.isAttacked = true;
turned++;
}
}
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
if (vis[r][c] == 1) board[r][c] = -1;
return turned;
}
static int[][] deepCopy(int[][] board) {
if (board.length <= 0) return new int[][] {};
int[][] tb = new int[board.length][board[0].length];
for (int i = 0; i < board.length;i++) {
tb[i] = board[i].clone();
}
return tb;
}
// 2. 메두사의 시선
static int stairing(int[][] board) {
// 빈 칸 : 0 // 메두사 : 1 // 전사 : 2 // 시선 : -1 // 안전지대 : 3
// 실제 돌 된 애들 개수
int max = Integer.MIN_VALUE;
int dir = -1;
// 2. 메두사의 시선
for (int i = 0 ;i < 4; i++) {
int[][] tempBoard = deepCopy(board);
int temp = mockSimulate(i, tempBoard);
if (temp > max) {
max = temp;
dir = i;
}
}
return simulate(dir, board);
}
static int calcDist(int r, int c, int nr, int nc) {
return Math.abs(nr - r) + Math.abs(nc -c);
}
// 3. 전사 이동
static int moveWarrior(int[][] board) {
int mr = medusa[0];
int mc = medusa[1];
int[] firstPriority = {0, 1, 2, 3};
int[] secondPriority = {2, 3, 0, 1};
int moveCnt = 0;
for (Warrior w : warriors) {
if (!w.isAlive) continue;
if (w.isAttacked) continue;
int cr = w.r;
int cc = w.c;
// 현재 거리
int curDist = calcDist(mr, mc, cr, cc);
// --- [1] 첫 번째 이동: "거리를 줄이는" 칸만 고려 ---
int minDist = Integer.MAX_VALUE;
int dir = -1;
for (int i : firstPriority) {
int nr = cr + dr[i];
int nc = cc + dc[i];
if (OOB(nr, nc)) continue;
if (board[nr][nc] == -1) continue;
int d = calcDist(mr, mc, nr, nc);
// 반드시 현재 거리보다 작아야 함
if (d < curDist) {
// tie는 firstPriority 순서대로 자연 해결
if (d < minDist) {
minDist = d;
dir = i;
}
}
}
if (dir != -1) {
cr += dr[dir];
cc += dc[dir];
moveCnt++;
w.r = cr;
w.c = cc;
curDist = minDist; // 현재 거리 업데이트
}
// --- 메두사에 도착했으면 더 이동하지 않음 ---
if (cr == mr && cc == mc) continue;
// --- [2] 두 번째 이동: 동일하게 "거리를 줄이는" 칸만 고려 ---
minDist = Integer.MAX_VALUE;
dir = -1;
for (int i : secondPriority) {
int nr = cr + dr[i];
int nc = cc + dc[i];
if (OOB(nr, nc)) continue;
if (board[nr][nc] == -1) continue;
int d = calcDist(mr, mc, nr, nc);
if (d < curDist) {
if (d < minDist) {
minDist = d;
dir = i;
}
}
}
if (dir != -1) {
cr += dr[dir];
cc += dc[dir];
moveCnt++;
w.r = cr;
w.c = cc;
}
}
return moveCnt;
}
// 4. 전사 공격
static int attack() {
// 4. 전사의 공격
// 메와 같은 칸 공격 but 사라짐
// if 메두사 공원 도착? 0 출력하고 프로그램 종료 --> 이거 앞에 가도 될 것 같은데
int attackCnt = 0;
for (Warrior w : warriors) {
if (!w.isAlive) continue;
if (w.r == medusa[0] && w.c == medusa[1]) {
attackCnt++;
w.isAlive = false;
}
}
return attackCnt;
}
// 5. 결과 출력
static void printResult(int totalDist, int rockCnt, int attackCnt) {
// 출력 :
// 전사가 이동한 거리의 합 --> 3번에서 계산
// 메두사로 인해 돌이 된 전사의 수 ---> 2단계 계산
// 메두사를 공격한 전사의 수 --> 4번에 계산
System.out.print(totalDist + " " + rockCnt + " " + attackCnt);
System.out.println("");
}
static void releaseWarrior() {
for (Warrior w : warriors) {
if (!w.isAlive) continue;
if (w.isAttacked) w.isAttacked = false;
}
}
}
메인 게임 루프
├── 턴별 탐사 시뮬레이션
│ ├── 회전 후보 평가 (우선순위: 각도 → 열 → 행)
│ │ ├── 90도 회전 후보들
│ │ │ ├── (1,1) 중심 3x3 회전
│ │ │ ├── (1,2) 중심 3x3 회전
│ │ │ └── ... (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)
│ │ ├── 180도 회전 후보들 (같은 순서)
│ │ └── 270도 회전 후보들 (같은 순서)
│ │
│ ├── 각 후보별 1차 획득 가치 계산
│ │ ├── 보드 딥카피
│ │ ├── 회전 적용 (rotate90 × degree회)
│ │ ├── 연결 그룹 찾기 (BFS)
│ │ │ ├── 방문하지 않은 각 칸에서 시작
│ │ │ ├── 같은 숫자인 인접 칸들을 그룹화
│ │ │ └── 그룹 크기 ≥ 3인 것만 수집
│ │ └── 총 제거될 유물 개수 반환 (연쇄 계산 X)
│ │
│ ├── 최적 회전 선택 (1차 획득 가치 최대)
│ └── 실제 보드에 최적 회전 적용
│
├── 연쇄 유물 획득 프로세스
│ ├── 유물 제거 루프 (제거할 것이 없을 때까지 반복)
│ │ ├── 연결 그룹 탐색 (BFS)
│ │ │ ├── 5×5 보드 전체 스캔
│ │ │ ├── 각 미방문 칸에서 같은 숫자 그룹 찾기
│ │ │ └── 크기 ≥ 3인 그룹들만 수집
│ │ │
│ │ ├── 유물 제거
│ │ │ ├── 선택된 그룹들의 모든 칸을 0으로 변경
│ │ │ └── 제거된 유물 개수 누적
│ │ │
│ │ ├── 새 유물 채우기 (열 우선 → 행 역순)
│ │ │ ├── 열 0부터 4까지 순회
│ │ │ ├── 각 열에서 행 4부터 0까지 역순 확인
│ │ │ ├── 빈 칸(0)을 발견하면 refill 배열에서 순서대로 채움
│ │ │ └── refillIdx 증가 (M 초과시 0으로 리셋)
│ │ │
│ │ └── 더 이상 제거할 그룹이 없으면 루프 종료
│ │
│ └── 턴별 총 획득 유물 개수 결과에 추가
│
├── 게임 종료 조건 확인
│ ├── 1차 획득 가치가 0인 경우 → 게임 종료
│ └── K턴 완료시 게임 종료
│
└── 결과 출력 (각 턴별 획득 유물 개수, 공백으로 구분)
rotate90(board, centerR, centerC):
├── 3×3 임시 배열에 원본 복사
├── 시계방향 90도 공식 적용: (i,j) → (j, 2-i)
└── 원본 보드에 회전 결과 덮어쓰기
findGroup(board, startR, startC, visited):
├── 시작점을 큐와 결과셋에 추가
├── BFS 루프
│ ├── 큐에서 현재 위치 제거
│ ├── 4방향 인접 칸 확인
│ │ ├── 경계 체크, 방문 체크, 같은 숫자 체크
│ │ ├── 조건 만족시 방문 표시 후 큐에 추가
│ │ └── 결과셋에도 추가
│ └── 큐가 빌 때까지 반복
└── 연결된 모든 칸들의 집합 반환
searching():
├── 3중 반복문 (올바른 순서)
│ ├── for degree (1→3): 각도 우선
│ ├── for col (1→3): 열 우선
│ └── for row (1→3): 행 우선
├── 각 조합별로 시뮬레이션 수행
├── 최대 획득 가치를 가진 조합 선택
└── 실제 보드에 최적 회전 적용 후 연쇄 획득 실행
// 메인 로직만 3개 함수로 구성
1. simulate() - 턴별 시뮬레이션
2. findBestRotation() - 최적 회전 찾기 (1차 획득만)
3. executeChainAcquisition() - 연쇄 획득 실행
import java.util.*;
import java.io.*;
public class Main {
static int K, M;
static int[][] board = new int[5][5];
static int[] refill;
static int refillIdx = 0;
static class Point implements Comparable<Point> {
int r, c;
Point(int r, int c) {
this.r = r;
this.c = c;
}
@Override
public int compareTo(Point o) {
if (r != o.r) return r - o.r;
return c - o.c;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Point)) return false;
Point p = (Point) o;
return r == p.r && c == p.c;
}
@Override
public int hashCode() {
return Objects.hash(r, c);
}
}
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
static int[][] deepCopy(int[][] board) {
int[][] tempBoard = new int[5][5];
for (int i = 0; i < 5; i++) {
tempBoard[i] = board[i].clone();
}
return tempBoard;
}
static boolean OOB(int r, int c) {
return (r < 0 || c < 0 || r >= 5 || c >= 5);
}
static void rotate90(int[][] bd, int r, int c) {
int[][] temp = new int[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
temp[i][j] = bd[r-1+i][c-1+j];
}
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
bd[r-1+i][c-1+j] = temp[3-1-j][i];
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < 5; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 5; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
refill = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
refill[i] = Integer.parseInt(st.nextToken());
}
List<Integer> results = new ArrayList<>();
for (int i = 0; i < K; i++) {
int bomul = simulate();
if (bomul == 0) break;
results.add(bomul);
}
// 결과 출력
for (int i = 0; i < results.size(); i++) {
System.out.print(results.get(i));
if (i < results.size() - 1) System.out.print(" ");
}
if (!results.isEmpty()) System.out.println();
}
static int simulate() {
return searching();
}
// 수정: 시뮬레이션에서는 첫 번째 획득만 계산 (연쇄 X)
static int searching() {
int maxBomul = -1;
int bestR = -1, bestC = -1, bestDegree = -1;
// 올바른 우선순위: 각도 → 열 → 행
for (int degree = 1; degree <= 3; degree++) {
for (int c = 1; c < 4; c++) {
for (int r = 1; r < 4; r++) {
int[][] tempBoard = deepCopy(board);
// 회전
for (int rot = 0; rot < degree; rot++) {
rotate90(tempBoard, r, c);
}
// 첫 번째 획득만 계산 (메모리 절약)
int bomul = getFirstAcquisition(tempBoard);
if (bomul > maxBomul) {
maxBomul = bomul;
bestR = r;
bestC = c;
bestDegree = degree;
}
}
}
}
if (maxBomul == 0) return 0;
// 실제 회전 및 연쇄 획득 실행
return executeRotation(board, bestR, bestC, bestDegree);
}
// 첫 번째 획득만 계산 (시뮬레이션용)
static int getFirstAcquisition(int[][] bd) {
List<Set<Point>> groups = new ArrayList<>();
boolean[][] visited = new boolean[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (visited[i][j]) continue;
visited[i][j] = true;
Set<Point> group = findGroup(bd, i, j, visited);
if (group.size() >= 3) {
groups.add(group);
}
}
}
int count = 0;
for (Set<Point> group : groups) {
count += group.size();
}
return count;
}
// 실제 실행용 (연쇄 획득)
static int executeRotation(int[][] bd, int r, int c, int degree) {
// 회전
for (int i = 0; i < degree; i++) {
rotate90(bd, r, c);
}
// 연쇄 획득
int totalBomul = 0;
while (true) {
List<Set<Point>> groups = new ArrayList<>();
boolean[][] visited = new boolean[5][5];
// 그룹 찾기
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (visited[i][j]) continue;
visited[i][j] = true;
Set<Point> group = findGroup(bd, i, j, visited);
if (group.size() >= 3) {
groups.add(group);
}
}
}
if (groups.isEmpty()) break;
// 그룹 제거
for (Set<Point> group : groups) {
for (Point p : group) {
bd[p.r][p.c] = 0;
totalBomul++;
}
}
// refill
for (int j = 0; j < 5; j++) {
for (int i = 4; i >= 0; i--) {
if (bd[i][j] == 0) {
bd[i][j] = refill[refillIdx];
refillIdx++;
if (refillIdx >= M) refillIdx = 0;
}
}
}
}
return totalBomul;
}
static Set<Point> findGroup(int[][] bd, int r, int c, boolean[][] visited) {
Set<Point> group = new HashSet<>(); // TreeSet 대신 HashSet 사용 (메모리 절약)
int groupId = bd[r][c];
ArrayDeque<Point> q = new ArrayDeque<>();
q.add(new Point(r, c));
group.add(new Point(r, c));
while (!q.isEmpty()) {
Point p = q.poll();
for (int i = 0; i < 4; i++) {
int nr = p.r + dr[i];
int nc = p.c + dc[i];
if (OOB(nr, nc)) continue;
if (visited[nr][nc]) continue;
if (bd[nr][nc] != groupId) continue;
visited[nr][nc] = true;
Point newPoint = new Point(nr, nc);
q.add(newPoint);
group.add(newPoint);
}
}
return group;
}
}
정령별 순차 탐사
├── 골렘 이동 시뮬레이션
│ ├── 초기 위치 설정 (r=1, c=입력받은열)
│ ├── 이동 루프 (더 이상 움직일 수 없을 때까지)
│ │ ├── 이동 우선순위 체크
│ │ │ ├── 1순위: 남쪽 한 칸 이동
│ │ │ │ ├── 조건: 골렘 아래 3칸 (중앙, 좌하, 우하) 모두 비어있음
│ │ │ │ └── 성공시: r++
│ │ │ │
│ │ │ ├── 2순위: 서쪽 회전하며 남쪽 이동
│ │ │ │ ├── 1단계: 서쪽 이동 가능 체크 (골렘 좌측 3칸)
│ │ │ │ ├── 2단계: 서쪽 이동 후 남쪽 이동 가능 체크
│ │ │ │ └── 성공시: c--, r++, 출구방향 반시계 회전
│ │ │ │
│ │ │ └── 3순위: 동쪽 회전하며 남쪽 이동
│ │ │ ├── 1단계: 동쪽 이동 가능 체크 (골렘 우측 3칸)
│ │ │ ├── 2단계: 동쪽 이동 후 남쪽 이동 가능 체크
│ │ │ └── 성공시: c++, r++, 출구방향 시계 회전
│ │ │
│ │ └── 모든 이동 불가능시 이동 종료
│ │
│ ├── 숲 이탈 여부 확인
│ │ ├── 골렘 상단부(r-1)가 숲 경계(3행) 밖에 있는지 체크
│ │ ├── 이탈시: 모든 골렘 제거 후 다음 정령으로
│ │ └── 정상시: 골렘 배치 및 정보 저장
│ │
│ └── 골렘 배치
│ ├── 십자가 모양으로 골렘ID 배치
│ ├── 골렘 정보 저장 (중심좌표, 출구방향)
│ └── 정령 탐사 단계로 진행
│
├── 정령 이동 시뮬레이션 (BFS)
│ ├── 초기 상태: 골렘 중심에서 시작
│ ├── BFS 탐색 루프
│ │ ├── 현재 위치에서 4방향 이동 시도
│ │ ├── 이동 조건 체크
│ │ │ ├── 경계 내부 & 미방문 & 빈칸 아님
│ │ │ ├── 같은 골렘 내 이동: 자유롭게 이동 가능
│ │ │ └── 다른 골렘으로 이동: 현재 위치가 출구여야 함
│ │ │ ├── 출구 확인: 현재 골렘의 중심+출구방향 = 현재위치
│ │ │ └── 출구에서만 인접한 다른 골렘으로 이동 가능
│ │ │
│ │ ├── 도달 가능한 모든 위치 탐색
│ │ └── 가장 남쪽 행번호 추적 및 갱신
│ │
│ └── 최대 남쪽 행번호 반환
│
└── 결과 누적 및 출력 (최대 행번호들의 총합)
골렘 이동 체크 (십자가 모양 5칸 고려):
├── 남쪽 이동 체크
│ ├── (r+2, c) : 골렘 아래 중앙
│ ├── (r+1, c-1) : 골렘 좌측 아래
│ └── (r+1, c+1) : 골렘 우측 아래
│
├── 서쪽 회전 이동 체크
│ ├── 1단계 서쪽 이동 가능성
│ │ ├── (r-1, c-1) : 좌상
│ │ ├── (r, c-2) : 좌측 끝
│ │ └── (r+1, c-1) : 좌하
│ └── 2단계 남쪽 이동 가능성
│ ├── (r+2, c-1) : 이동 후 아래 중앙
│ └── (r+1, c-2) : 이동 후 좌측 아래
│
└── 동쪽 회전 이동 (대칭 구조)
정령 이동 규칙:
├── 같은 골렘 내부: 제한 없이 이동
├── 골렘간 이동: 출구를 통해서만 가능
│ ├── 출구 확인 공식: (중심r + dr[출구방향], 중심c + dc[출구방향])
│ └── 출구에서 인접한 다른 골렘의 아무 부분으로 이동
└── 목표: 네트워크상 가장 남쪽 지점 탐색
좌표계 구조 (R+3 × C+1):
├── 인덱스 0~2: 골렘 진입용 여유공간
├── 인덱스 3~R+2: 실제 숲 영역 (1행~R행)
├── 골렘 중심이 인덱스 1에서 시작 (북쪽 끝에서 진입)
└── 결과 변환: 배열인덱스 - 2 = 실제 행번호
골렘별 정보 저장:
├── golemR[id]: 골렘 중심의 행좌표
├── golemC[id]: 골렘 중심의 열좌표
├── golemDir[id]: 출구 방향 (0~3: 북동남서)
└── forest[r][c]: 각 칸의 골렘ID (0=빈칸)
isEmpty(r, c) 체크:
├── 경계 확인: 1 ≤ c ≤ C, r ≤ R+2
├── 빈칸 확인: forest[r][c] == 0
└── 골렘 배치시 십자가 5칸 모두 체크
출구 확인 메커니즘:
├── 골렘 중심 좌표 + 방향벡터 = 출구 좌표
├── 정령이 출구에 있을 때만 다른 골렘 이동 가능
└── BFS에서 이동 조건으로 활용
import java.util.*;
import java.io.*;
public class Main {
static int R, C, K;
static int[][] forest;
// 북, 동, 남, 서
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
static int result = 0;
// 각 골렘의 정보 저장 (중심 r, c, 출구 방향)
static int[] golemR, golemC, golemDir;
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());
forest = new int[R+3][C+1]; // 위쪽 여유공간 추가
golemR = new int[K+1];
golemC = new int[K+1];
golemDir = new int[K+1];
for (int i = 1; i <= K; i++) {
st = new StringTokenizer(br.readLine());
int ci = Integer.parseInt(st.nextToken());
int di = Integer.parseInt(st.nextToken());
simulate(i, ci, di);
}
System.out.println(result);
}
static void simulate(int golemId, int startCol, int exitDir) {
// 골렘 시작 위치 (r=1, c=startCol)
int r = 1;
int c = startCol;
int dir = exitDir;
// 1. 골렘 이동
while (true) {
boolean moved = false;
// 1) 남쪽으로 한 칸 이동
if (canMoveSouth(r, c)) {
r++;
moved = true;
}
// 2) 서쪽으로 회전하며 남쪽 이동
else if (canMoveWestAndSouth(r, c)) {
c--;
r++;
dir = (dir + 3) % 4; // 반시계방향 회전
moved = true;
}
// 3) 동쪽으로 회전하며 남쪽 이동
else if (canMoveEastAndSouth(r, c)) {
c++;
r++;
dir = (dir + 1) % 4; // 시계방향 회전
moved = true;
}
if (!moved) break; // 더 이상 움직일 수 없음
}
// 골렘이 숲을 벗어난 상태인지 확인
if (r - 1 < 3) { // 골렘의 맨 위쪽이 숲 밖에 있음
// 숲 초기화
forest = new int[R+3][C+1];
// 골렘 정보 초기화
Arrays.fill(golemR, 0);
Arrays.fill(golemC, 0);
Arrays.fill(golemDir, 0);
return;
}
// 골렘을 숲에 배치하고 정보 저장
placeGolem(r, c, golemId);
golemR[golemId] = r;
golemC[golemId] = c;
golemDir[golemId] = dir;
// 2. 정령 이동 - 가장 남쪽까지
int maxRow = findMaxRow(r, c);
result += (maxRow - 2); // 실제 행 번호로 변환
}
// 남쪽으로 이동 가능한지 확인
static boolean canMoveSouth(int r, int c) {
return isEmpty(r+2, c) && isEmpty(r+1, c-1) && isEmpty(r+1, c+1);
}
// 서쪽으로 회전하며 남쪽 이동 가능한지 확인
static boolean canMoveWestAndSouth(int r, int c) {
// 서쪽으로 이동 가능하고
if (!isEmpty(r-1, c-1) || !isEmpty(r, c-2) || !isEmpty(r+1, c-1)) {
return false;
}
// 서쪽 이동 후 남쪽으로 이동 가능한지
return isEmpty(r+2, c-1) && isEmpty(r+1, c-2);
}
// 동쪽으로 회전하며 남쪽 이동 가능한지 확인
static boolean canMoveEastAndSouth(int r, int c) {
// 동쪽으로 이동 가능하고
if (!isEmpty(r-1, c+1) || !isEmpty(r, c+2) || !isEmpty(r+1, c+1)) {
return false;
}
// 동쪽 이동 후 남쪽으로 이동 가능한지
return isEmpty(r+2, c+1) && isEmpty(r+1, c+2);
}
// 해당 위치가 비어있는지 확인
static boolean isEmpty(int r, int c) {
if (c < 1 || c > C || r > R+2) return false; // 경계 체크
return forest[r][c] == 0;
}
// 골렘을 숲에 배치
static void placeGolem(int r, int c, int golemId) {
forest[r][c] = golemId; // 중심
forest[r-1][c] = golemId; // 북
forest[r+1][c] = golemId; // 남
forest[r][c-1] = golemId; // 서
forest[r][c+1] = golemId; // 동
}
// BFS로 정령이 갈 수 있는 가장 남쪽 위치 찾기
static int findMaxRow(int startR, int startC) {
Queue<int[]> queue = new ArrayDeque<>();
boolean[][] visited = new boolean[R+3][C+1];
queue.offer(new int[]{startR, startC});
visited[startR][startC] = true;
int maxRow = startR;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int r = curr[0];
int c = curr[1];
maxRow = Math.max(maxRow, r);
// 4방향으로 이동
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 1 || nr > R+2 || nc < 1 || nc > C) continue;
if (visited[nr][nc]) continue;
if (forest[nr][nc] == 0) continue; // 빈 공간은 이동 불가
int currentGolemId = forest[r][c];
int nextGolemId = forest[nr][nc];
// 같은 골렘 내에서 이동
if (nextGolemId == currentGolemId) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
// 다른 골렘으로 이동 - 현재 위치가 출구여야 함
else if (isExit(r, c, currentGolemId)) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
return maxRow;
}
// 현재 위치가 골렘의 출구인지 확인
static boolean isExit(int r, int c, int golemId) {
if (golemId <= 0 || golemId > K) return false;
if (golemR[golemId] == 0) return false; // 골렘이 배치되지 않음
int centerR = golemR[golemId];
int centerC = golemC[golemId];
int exitDir = golemDir[golemId];
int exitR = centerR + dr[exitDir];
int exitC = centerC + dc[exitDir];
return (r == exitR && c == exitC);
}
}
미지의 공간 탈출 시스템
├── Phase 1: 시간의 벽 표면 탐색 (3D BFS)
│ ├── 초기 설정
│ │ ├── 5면 큐브 구조 파악
│ │ │ ├── 동면(EAST), 서면(WEST), 남면(SOUTH), 북면(NORTH), 윗면(TOP)
│ │ │ ├── 각 면은 M×M 격자로 구성
│ │ │ └── 0: 빈공간, 1: 벽, 2: 시작점(윗면)
│ │ │
│ │ ├── 시작점 탐색 및 설정
│ │ │ ├── 윗면에서 값 2인 칸 찾기 (타임머신 위치)
│ │ │ ├── 해당 칸을 0으로 변경 (이동 가능하도록)
│ │ │ └── BFS 시작점으로 설정 (TOP, startR, startC)
│ │ │
│ │ └── 목표 지점 계산
│ │ ├── 미지의 공간에서 시간의 벽(3) 위치 찾기
│ │ ├── 시간의 벽 주변 4방향에서 출구(0) 탐색
│ │ │ ├── 북쪽 출구: wallBaseR-1 행에서 탐색
│ │ │ ├── 남쪽 출구: wallBaseR+M 행에서 탐색
│ │ │ ├── 서쪽 출구: wallBaseC-1 열에서 탐색
│ │ │ └── 동쪽 출구: wallBaseC+M 열에서 탐색
│ │ └── 출구를 큐브 면의 상대좌표로 변환
│ │
│ ├── 3D 표면 BFS 탐색
│ │ ├── BFS 큐 초기화 (시작점부터)
│ │ ├── 3차원 방문 배열 [5][M][M]
│ │ │
│ │ ├── 탐색 루프 (목표 도달까지)
│ │ │ ├── 현재 상태: (시간, 면, 행, 열)
│ │ │ │
│ │ │ ├── 같은 면 내 이동 (4방향)
│ │ │ │ ├── 상하좌우 이동 시도
│ │ │ │ ├── 면 경계 확인 (0 ≤ r,c < M)
│ │ │ │ ├── 빈공간(0) 여부 확인
│ │ │ │ └── 미방문 여부 확인
│ │ │ │
│ │ │ └── 면간 이동 (복잡한 3D 기하학)
│ │ │ ├── 윗면 → 4개 옆면 이동 규칙
│ │ │ │ ├── r=0 (북쪽 가장자리) → 북면 (열 반전)
│ │ │ │ ├── r=M-1 (남쪽 가장자리) → 남면 (열 유지)
│ │ │ │ ├── c=0 (서쪽 가장자리) → 서면 (행 유지)
│ │ │ │ └── c=M-1 (동쪽 가장자리) → 동면 (행 반전)
│ │ │ │
│ │ │ ├── 옆면 → 윗면 이동 규칙
│ │ │ │ ├── 각 면의 r=0 (윗쪽 가장자리)에서 윗면으로
│ │ │ │ └── 좌표 변환: 반전/회전 규칙 적용
│ │ │ │
│ │ │ └── 옆면 ↔ 옆면 이동 규칙
│ │ │ ├── 인접한 면의 세로 가장자리 연결
│ │ │ └── 복잡한 좌표 매핑 (북-동-남-서 순환)
│ │ │
│ │ ├── 목표 도달 확인
│ │ │ ├── 계산된 목표 면과 좌표에 도달했는지 확인
│ │ │ ├── 도달시: timeToExitWall = time + 1
│ │ │ └── 미지의 공간 출구 좌표와 함께 반환
│ │ │
│ │ └── 탈출 실패시 -1 반환
│ │
├── Phase 2: 미지의 공간 횡단 (2D BFS + 시간 제약)
│ ├── 시간 이상 현상 전처리
│ │ ├── 각 이상 현상별 확산 경로 계산
│ │ │ ├── 시작점: (r_i, c_i)
│ │ │ ├── 방향: d_i (0:동, 1:서, 2:남, 3:북)
│ │ │ ├── 속도: v_i (v_i 시간마다 1칸씩 확산)
│ │ │ └── 확산 경로: 직선으로 장애물/경계까지
│ │ │
│ │ ├── anomalyBlocks[r][c] 배열 구성
│ │ │ ├── 각 칸이 막히는 가장 빠른 시간 기록
│ │ │ ├── 초기값: Integer.MAX_VALUE (막히지 않음)
│ │ │ ├── 이상 현상 시작점: 0 시간부터 차단
│ │ │ └── 확산 경로: 각 단계별 차단 시간 계산
│ │ │
│ │ └── 예외 처리
│ │ ├── 탈출구(4)는 절대 막히지 않음
│ │ ├── 장애물(1), 시간의벽(3)에서 확산 중단
│ │ └── 격자 경계에서 확산 중단
│ │
│ ├── 동적 2D BFS 탐색
│ │ ├── 시작 상태 설정
│ │ │ ├── 시작점: Phase 1에서 구한 출구 좌표
│ │ │ ├── 시작 시간: timeToExitWall
│ │ │ └── 목표: 최종 탈출구(4) 찾기
│ │ │
│ │ ├── 최적 경로 BFS
│ │ │ ├── 큐: (시간, 행, 열) 상태 저장
│ │ │ ├── visited[r][c]: 각 칸 도달 최소 시간 기록
│ │ │ │
│ │ │ ├── 탐색 루프
│ │ │ │ ├── 현재 상태: (time, r, c)
│ │ │ │ ├── 최종 탈출구 도달시 시간 반환
│ │ │ │ │
│ │ │ │ └── 4방향 이동 시도
│ │ │ │ ├── 다음 좌표: (nr, nc)
│ │ │ │ ├── 다음 시간: nextTime = time + 1
│ │ │ │ │
│ │ │ │ ├── 이동 가능 조건 확인
│ │ │ │ │ ├── 격자 범위 내 (0 ≤ nr,nc < N)
│ │ │ │ │ ├── 장애물 아님 (≠ 1, ≠ 3)
│ │ │ │ │ ├── 시간 제약 만족 (nextTime < anomalyBlocks[nr][nc])
│ │ │ │ │ └── 더 빠른 경로 (nextTime < visited[nr][nc])
│ │ │ │ │
│ │ │ │ └── 조건 만족시 큐에 추가
│ │ │ │
│ │ │ └── 모든 경로 탐색 완료시 -1 반환
│ │ │
│ │ └── 핵심 최적화 요소
│ │ ├── 시간 종속적 장애물 회피
│ │ ├── 다익스트라 유사 최적 경로 추적
│ │ └── 동적 계획법으로 중복 계산 제거
│ │
└── 최종 결과 출력
├── Phase 1 실패시: -1
├── Phase 2 실패시: -1
└── 성공시: 총 소요 시간
동적 장애물 생성 알고리즘:
├── 각 이상 현상 (r_i, c_i, d_i, v_i)
│ ├── 시작점에서 0시간부터 차단
│ ├── d_i 방향으로 직선 확산
│ ├── v_i 시간마다 1칸씩 진행
│ └── 장애물/경계/탈출구에서 중단
│
├── 확산 경로 계산
│ ├── timeStep = 0부터 시작
│ ├── 매 단계: timeStep += v_i
│ ├── 위치: (r + step*dr[d], c + step*dc[d])
│ └── anomalyBlocks[r][c] = min(기존값, timeStep)
│
└── 특수 규칙
├── 탈출구(4): 절대 차단되지 않음
├── 여러 현상 중복: 가장 빠른 차단 시간 적용
└── 차단되지 않은 칸: Integer.MAX_VALUE 유지
import java.io.BufferedReader; // 입력을 효율적으로 읽기 위해 BufferedReader 사용
import java.io.IOException; // 입출력 예외 처리를 위해 IOException 임포트
import java.io.InputStreamReader; // 표준 입력을 읽기 위해 InputStreamReader 임포트
import java.util.ArrayDeque; // 큐 구현을 위해 ArrayDeque 사용 (Deque 인터페이스 구현)
import java.util.ArrayList; // 동적 배열 리스트를 위해 ArrayList 사용
import java.util.Deque; // 큐 인터페이스를 위해 Deque 임포트
import java.util.List; // 리스트 인터페이스를 위해 List 임포트
import java.util.StringTokenizer; // 문자열을 토큰으로 분리하기 위해 StringTokenizer 사용
public class Main {
// 전역 변수 선언
static int N, M, F; // N: 미지의 공간 크기, M: 시간의 벽 크기, F: 시간 이상 현상 개수
static int[][] spaceGrid; // 미지의 공간 평면도 (N x N)
static int[][][] views; // 시간의 벽 단면도 (5개 면, 각 M x M)
static List<int[]> anomalies; // 시간 이상 현상 정보 리스트 (r, c, d, v)
// 면(face) 인덱스 상수 정의 (가독성을 위해)
// views 배열의 인덱스와 매핑됩니다.
static final int EAST = 0;
static final int WEST = 1;
static final int SOUTH = 2;
static final int NORTH = 3;
static final int TOP = 4;
// BFS 탐색을 위한 상태 클래스 (Phase 1: 시간의 벽 표면 이동)
static class State3D {
int time; // 현재까지 걸린 시간
int face; // 현재 위치한 면 (EAST, WEST, SOUTH, NORTH, TOP)
int r; // 현재 면 내의 행 좌표
int c; // 현재 면 내의 열 좌표
public State3D(int time, int face, int r, int c) {
this.time = time;
this.face = face;
this.r = r;
this.c = c;
}
}
// BFS 탐색을 위한 상태 클래스 (Phase 2: 미지의 공간 횡단)
static class State2D {
int time; // 현재까지 걸린 시간
int r; // 미지의 공간 내의 행 좌표
int c; // 미지의 공간 내의 열 좌표
public State2D(int time, int r, int c) {
this.time = time;
this.r = r;
this.c = c;
}
}
// 입력 처리 함수
static void readInput() 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());
F = Integer.parseInt(st.nextToken());
spaceGrid = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
spaceGrid[i][j] = Integer.parseInt(st.nextToken());
}
}
views = new int[5][M][M];
for (int i = 0; i < 5; i++) {
for (int r = 0; r < M; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 0; c < M; c++) {
views[i][r][c] = Integer.parseInt(st.nextToken());
}
}
}
anomalies = new ArrayList<>();
for (int i = 0; i < F; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
anomalies.add(new int[]{r, c, d, v});
}
}
/**
* 미지의 공간 평면도에서 시간의 벽과 맞닿은 유일한 출구를 찾고,
* 해당 출구가 시간의 벽의 어느 면의 어느 상대 좌표에 해당하는지 매핑합니다.
* @param wallBaseR 시간의 벽 좌상단 행 좌표
* @param wallBaseC 시간의 벽 좌상단 열 좌표
* @return [planeExitR, planeExitC, goalFace, goalR, goalC] 배열. 찾지 못하면 모두 -1.
*/
static int[] findExitAndGoal(int wallBaseR, int wallBaseC) {
int planeExitR = -1, planeExitC = -1; // 미지의 공간 평면도 상의 출구 좌표
int goalFace = -1, goalR = -1, goalC = -1; // 시간의 벽 면에서의 상대 좌표
// 북쪽 출구 탐색: 시간의 벽 위쪽 (wallBaseR - 1) 행
if (wallBaseR > 0) {
for (int cOff = 0; cOff < M; cOff++) { // 벽의 열 범위 (wallBaseC ~ wallBaseC + M - 1)
if (spaceGrid[wallBaseR - 1][wallBaseC + cOff] == 0) { // 빈 공간(0)인지 확인
planeExitR = wallBaseR - 1;
planeExitC = wallBaseC + cOff;
// 북쪽 면에서 출구는 r=M-1 (가장 아래), c는 윗면에서 봤을 때의 c와 반대 방향으로 매핑됨 (M-1-cOff)
goalFace = NORTH;
goalR = M - 1;
goalC = M - cOff - 1;
break;
}
}
}
if (goalFace != -1) return new int[]{planeExitR, planeExitC, goalFace, goalR, goalC};
// 남쪽 출구 탐색: 시간의 벽 아래쪽 (wallBaseR + M) 행
if (wallBaseR + M < N) {
for (int cOff = 0; cOff < M; cOff++) { // 벽의 열 범위 (wallBaseC ~ wallBaseC + M - 1)
if (spaceGrid[wallBaseR + M][wallBaseC + cOff] == 0) {
planeExitR = wallBaseR + M;
planeExitC = wallBaseC + cOff;
// 남쪽 면에서 출구는 r=M-1 (가장 아래), c는 벽의 cOff와 동일하게 매핑
goalFace = SOUTH;
goalR = M - 1;
goalC = cOff;
break;
}
}
}
if (goalFace != -1) return new int[]{planeExitR, planeExitC, goalFace, goalR, goalC};
// 서쪽 출구 탐색: 시간의 벽 왼쪽 (wallBaseC - 1) 열
if (wallBaseC > 0) {
for (int rOff = 0; rOff < M; rOff++) { // 벽의 행 범위 (wallBaseR ~ wallBaseR + M - 1)
if (spaceGrid[wallBaseR + rOff][wallBaseC - 1] == 0) {
planeExitR = wallBaseR + rOff;
planeExitC = wallBaseC - 1;
// 서쪽 면에서 출구는 r=M-1 (가장 아래), c는 벽의 rOff와 동일하게 매핑
goalFace = WEST;
goalR = M - 1;
goalC = rOff;
break;
}
}
}
if (goalFace != -1) return new int[]{planeExitR, planeExitC, goalFace, goalR, goalC};
// 동쪽 출구 탐색: 시간의 벽 오른쪽 (wallBaseC + M) 열
if (wallBaseC + M < N) {
for (int rOff = 0; rOff < M; rOff++) { // 벽의 행 범위 (wallBaseR ~ wallBaseR + M - 1)
if (spaceGrid[wallBaseR + rOff][wallBaseC + M] == 0) {
planeExitR = wallBaseR + rOff;
planeExitC = wallBaseC + M;
// 동쪽 면에서 출구는 r=M-1 (가장 아래), c는 윗면에서 봤을 때의 r과 반대 방향으로 매핑됨 (M-1-rOff)
goalFace = EAST;
goalR = M - 1;
goalC = M - rOff - 1;
break;
}
}
}
if (goalFace != -1) return new int[]{planeExitR, planeExitC, goalFace, goalR, goalC};
// 모든 방향을 탐색했지만 출구를 찾지 못한 경우
return new int[]{-1, -1, -1, -1, -1};
}
/**
* Phase 1: 시간의 벽 표면을 탈출하는 최소 시간을 계산합니다.
* @return [timeToExitWall, planeExitR, planeExitC] 배열. 탈출 불가능 시 timeToExitWall은 -1.
*/
static int[] calcEscapeTime3D() {
// 1-1. 시작점과 목표 지점 설정
// 타임머신 시작 위치 찾기 (윗면에서 2로 표시된 곳)
int startFace = -1, startR = -1, startC = -1;
for (int r = 0; r < M; r++) {
for (int c = 0; c < M; c++) {
if (views[TOP][r][c] == 2) {
startFace = TOP;
startR = r;
startC = c;
views[TOP][r][c] = 0; // 시작점은 이제 빈 공간으로 간주하여 BFS 탐색에 방해되지 않도록 합니다.
break;
}
}
if (startFace != -1) break; // 시작점을 찾았으면 루프 종료
}
// 미지의 공간 평면도에서 시간의 벽(3)의 좌상단 위치 찾기
int wallBaseR = -1, wallBaseC = -1;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (spaceGrid[r][c] == 3) {
wallBaseR = r;
wallBaseC = c;
break;
}
}
if (wallBaseR != -1) break;
}
// 시간의 벽에서 미지의 공간으로 이어지는 출구 (planeExit)와
// 그 출구에 해당하는 시간의 벽 옆면의 상대 좌표 (goalFace, goalR, goalC) 찾기
int[] exitInfo = findExitAndGoal(wallBaseR, wallBaseC);
int planeExitR = exitInfo[0];
int planeExitC = exitInfo[1];
int goalFace = exitInfo[2];
int goalR = exitInfo[3];
int goalC = exitInfo[4];
// 출구를 찾지 못했거나, 찾은 출구가 시간의 벽 단면도 상에서 장애물인 경우 탈출 불가능
if (goalFace == -1 || views[goalFace][goalR][goalC] == 1) {
return new int[]{-1, -1, -1};
}
// 1-2. 표면 이동 BFS (Deque 사용)
// 큐: (현재 시간, 현재 면, 현재 면 내의 행, 현재 면 내의 열)을 저장하는 State3D 객체
Deque<State3D> qSurf = new ArrayDeque<>();
qSurf.add(new State3D(0, startFace, startR, startC));
// 방문 기록: (면, 행, 열) 튜플을 저장하는 3차원 boolean 배열. 중복 탐색 방지.
boolean[][][] visitedSurf = new boolean[5][M][M];
visitedSurf[startFace][startR][startC] = true;
int timeToExitWall = -1; // 시간의 벽을 탈출하는 데 걸리는 시간
// 상하좌우 이동을 위한 방향 배열
int[] dr = {-1, 1, 0, 0}; // 상, 하, 좌, 우
int[] dc = {0, 0, -1, 1}; // 상, 하, 좌, 우
while (!qSurf.isEmpty()) {
State3D current = qSurf.poll();
int time = current.time;
int face = current.face;
int r = current.r;
int c = current.c;
// 목표 지점(시간의 벽 출구)에 도달했으면 시간 기록 후 BFS 종료
// +1을 하는 이유는, 해당 칸에 도달하는 데 걸린 시간(time)에 1턴을 더하여
// 다음 턴에 미지의 공간 바닥으로 내려갈 수 있음을 의미합니다.
if (face == goalFace && r == goalR && c == goalC) {
timeToExitWall = time + 1;
break;
}
// 1. 같은 면 내에서 이동 (상하좌우 4방향)
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
// 면 내 유효 범위 확인 (0 <= nr, nc < M)
if (nr >= 0 && nr < M && nc >= 0 && nc < M) {
// 이동할 칸이 빈 공간(0)이고 아직 방문하지 않았다면
if (views[face][nr][nc] == 0 && !visitedSurf[face][nr][nc]) {
visitedSurf[face][nr][nc] = true; // 방문 기록
qSurf.add(new State3D(time + 1, face, nr, nc)); // 큐에 추가 (시간 1 증가)
}
}
}
// 2. 다른 면으로 이동 (면의 가장자리에서 인접한 면으로)
// (다음 면, 다음 면 내의 행, 다음 면 내의 열) 튜플 리스트
List<int[]> transitions = new ArrayList<>();
// 윗면(TOP)에서 다른 면으로 이동 규칙
if (face == TOP) {
if (r == 0) transitions.add(new int[]{NORTH, 0, M - c - 1}); // 윗면의 0행(북쪽 가장자리) -> 북쪽 면의 0행 (열은 반전)
if (r == M - 1) transitions.add(new int[]{SOUTH, 0, c}); // 윗면의 M-1행(남쪽 가장자리) -> 남쪽 면의 0행 (열은 그대로)
if (c == 0) transitions.add(new int[]{WEST, 0, r}); // 윗면의 0열(서쪽 가장자리) -> 서쪽 면의 0행 (행은 그대로)
if (c == M - 1) transitions.add(new int[]{EAST, 0, M - r - 1}); // 윗면의 M-1열(동쪽 가장자리) -> 동쪽 면의 0행 (행은 반전)
}
// 북쪽 면(NORTH)에서 다른 면으로 이동 규칙
else if (face == NORTH) {
if (r == 0) transitions.add(new int[]{TOP, 0, M - c - 1}); // 북쪽 면의 0행 -> 윗면의 0행 (열은 반전)
if (c == M - 1) transitions.add(new int[]{WEST, r, 0}); // 북쪽 면의 M-1열 -> 서쪽 면의 r행 (0열)
if (c == 0) transitions.add(new int[]{EAST, r, M - 1}); // 북쪽 면의 0열 -> 동쪽 면의 r행 (M-1열)
}
// 남쪽 면(SOUTH)에서 다른 면으로 이동 규칙
else if (face == SOUTH) {
if (r == 0) transitions.add(new int[]{TOP, M - 1, c}); // 남쪽 면의 0행 -> 윗면의 M-1행 (열은 그대로)
if (c == 0) transitions.add(new int[]{WEST, r, M - 1}); // 남쪽 면의 0열 -> 서쪽 면의 r행 (M-1열)
if (c == M - 1) transitions.add(new int[]{EAST, r, 0}); // 남쪽 면의 M-1열 -> 동쪽 면의 r행 (0열)
}
// 서쪽 면(WEST)에서 다른 면으로 이동 규칙
else if (face == WEST) {
if (r == 0) transitions.add(new int[]{TOP, c, 0}); // 서쪽 면의 0행 -> 윗면의 c열 (0행)
if (c == 0) transitions.add(new int[]{NORTH, r, M - 1}); // 서쪽 면의 0열 -> 북쪽 면의 r행 (M-1열)
if (c == M - 1) transitions.add(new int[]{SOUTH, r, 0}); // 서쪽 면의 M-1열 -> 남쪽 면의 r행 (0열)
}
// 동쪽 면(EAST)에서 다른 면으로 이동 규칙
else if (face == EAST) {
if (r == 0) transitions.add(new int[]{TOP, M - c - 1, M - 1}); // 동쪽 면의 0행 -> 윗면의 M-1열 (행은 반전)
if (c == M - 1) transitions.add(new int[]{NORTH, r, 0}); // 동쪽 면의 M-1열 -> 북쪽 면의 r행 (0열)
if (c == 0) transitions.add(new int[]{SOUTH, r, M - 1}); // 동쪽 면의 0열 -> 남쪽 면의 r행 (M-1열)
}
for (int[] next : transitions) {
int nextFace = next[0];
int nextR = next[1];
int nextC = next[2];
// 이동할 칸이 빈 공간(0)이고 아직 방문하지 않았다면
if (views[nextFace][nextR][nextC] == 0 && !visitedSurf[nextFace][nextR][nextC]) {
visitedSurf[nextFace][nextR][nextC] = true; // 방문 기록
qSurf.add(new State3D(time + 1, nextFace, nextR, nextC)); // 큐에 추가 (시간 1 증가)
}
}
}
// 시간의 벽을 탈출하는데 걸린 시간과 출구 좌표 반환
return new int[]{timeToExitWall, planeExitR, planeExitC};
}
/**
* Phase 2: 미지의 공간을 횡단하여 최종 탈출구까지 가는 최소 시간을 계산합니다.
* @param timeToExitWall 시간의 벽을 탈출하는 데 걸린 시간
* @param planeExitR 시간의 벽 출구의 미지의 공간 내 행 좌표
* @param planeExitC 시간의 벽 출구의 미지의 공간 내 열 좌표
* @return 최종 탈출 시간. 탈출 불가능 시 -1.
*/
static int calcDestTime2D(int timeToExitWall, int planeExitR, int planeExitC) {
// Phase 1에서 탈출에 실패했다면, Phase 2도 불가능
if (timeToExitWall == -1) {
return -1;
}
// 미지의 공간 평면도에서 최종 탈출구(4) 위치 찾기
int escapeR = -1, escapeC = -1;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (spaceGrid[r][c] == 4) {
escapeR = r;
escapeC = c;
break;
}
}
if (escapeR != -1) break;
}
// 시간 이상 현상에 의해 각 칸이 언제부터 막히는지 기록하는 배열
// anomalyBlocks[r][c] = (r,c) 칸이 막히는 가장 빠른 시간
// 초기값은 Integer.MAX_VALUE로 설정하여, 막히지 않는 칸은 계속 이 값을 가집니다.
int[][] anomalyBlocks = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
anomalyBlocks[i][j] = Integer.MAX_VALUE;
}
}
// 시간 이상 현상 확산 방향 (동, 서, 남, 북)
// 문제에서 주어진 방향: 동(0), 서(1), 남(2), 북(3)
int[] anomalyDr = {0, 0, 1, -1}; // 동, 서, 남, 북 (행 변화)
int[] anomalyDc = {1, -1, 0, 0}; // 동, 서, 남, 북 (열 변화)
// 각 시간 이상 현상에 대해 확산 경로 및 차단 시간 전처리
for (int[] anomaly : anomalies) {
int r_i = anomaly[0];
int c_i = anomaly[1];
int d_i = anomaly[2];
int v_i = anomaly[3];
// 시작 위치가 탈출구(4)가 아닌 경우에만 시간 이상 현상으로 막힐 수 있음
if (spaceGrid[r_i][c_i] != 4) {
anomalyBlocks[r_i][c_i] = Math.min(anomalyBlocks[r_i][c_i], 0);
}
int timeStep = 0; // 첫 확산 시간
int nextR = r_i;
int nextC = c_i;
while (true) {
nextR += anomalyDr[d_i];
nextC += anomalyDc[d_i];
timeStep += v_i; // 다음 확산 시간
// 격자 범위를 벗어나거나, 장애물(1)이거나, 시간의 벽(3)이거나, 탈출구(4)인 경우 확산 중단
// (시간의 벽은 2D 평면에서 장애물로 간주)
if (!(nextR >= 0 && nextR < N && nextC >= 0 && nextC < N) ||
spaceGrid[nextR][nextC] == 1 || spaceGrid[nextR][nextC] == 3 || spaceGrid[nextR][nextC] == 4) {
break;
}
// 해당 칸이 막히는 가장 빠른 시간을 갱신
anomalyBlocks[nextR][nextC] = Math.min(anomalyBlocks[nextR][nextC], timeStep);
}
}
// BFS 큐: (현재 시간, 현재 행, 현재 열)을 저장하는 State2D 객체
// 시작 시간은 시간의 벽을 탈출하는 데 걸린 시간입니다.
Deque<State2D> q2D = new ArrayDeque<>();
q2D.add(new State2D(timeToExitWall, planeExitR, planeExitC));
// 같은 칸이라도 더 빠른 시간에 도달하는 경로가 있다면 갱신하기 위함입니다.
// visited2D[r][c]는 (r,c)에 도달하는 최소 시간을 저장합니다.
int[][] visited2D = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
visited2D[i][j] = Integer.MAX_VALUE;
}
}
visited2D[planeExitR][planeExitC] = timeToExitWall;
// 상하좌우 이동을 위한 방향 배열
int[] dr = new int[]{-1, 1, 0, 0}; // 상, 하, 좌, 우
int[] dc = new int[]{0, 0, -1, 1}; // 상, 하, 좌, 우
while (!q2D.isEmpty()) {
State2D current = q2D.poll();
int time = current.time;
int cr = current.r;
int cc = current.c;
// 최종 탈출구에 도달했으면 현재 시간 반환
if (cr == escapeR && cc == escapeC) {
return time;
}
// 상하좌우 4방향 이동
for (int i = 0; i < 4; i++) {
int nr = cr + dr[i];
int nc = cc + dc[i];
int nextTime = time + 1; // 다음 칸으로 이동하는 데 걸리는 시간
// 이동 조건 확인:
// 1. 격자 범위 내에 있는지
// 2. 장애물(1)이나 시간의 벽(3)이 아닌지 (시간의 벽은 2D 평면에서 장애물로 간주)
// 3. 다음 시간에 해당 칸이 시간 이상 현상으로 막히지 않는지 (nextTime < anomalyBlocks[nr][nc])
// 4. 이미 방문했더라도 현재 경로가 더 빠른지 (nextTime < visited2D[nr][nc])
if ((nr >= 0 && nr < N && nc >= 0 && nc < N) &&
spaceGrid[nr][nc] != 1 && spaceGrid[nr][nc] != 3 &&
nextTime < anomalyBlocks[nr][nc] &&
nextTime < visited2D[nr][nc]) {
// 이동 가능하면 방문 기록 갱신 및 큐에 추가
visited2D[nr][nc] = nextTime;
q2D.add(new State2D(nextTime, nr, nc));
}
}
}
// 모든 경로를 탐색했지만 탈출구에 도달하지 못했다면 -1 반환
return -1;
}
// 메인 실행 함수
public static void main(String[] args) throws IOException {
readInput(); // 입력 읽기
// Phase 1: 시간의 벽 표면 탈출 시간 계산
int[] phase1Result = calcEscapeTime3D();
int timeToExitWall = phase1Result[0];
int planeExitR = phase1Result[1];
int planeExitC = phase1Result[2];
// Phase 2: 미지의 공간 횡단 시간 계산
int timeToGoal = calcDestTime2D(timeToExitWall, planeExitR, planeExitC);
System.out.println(timeToGoal); // 최종 시간 출력
}
}