Floyd-Warshall, 시뮬레이션
1. 오늘의 학습 흐름
- 플로이드-워셜 (Floyd-Warshall) - 모든 쌍 최단 경로
- BOJ 17143 낚시왕 (시뮬레이션)
- BOJ 1062 가르침 (BackTracking + BitMask)
- BOJ 14503 로봇청소기 (시뮬레이션 + 재귀)
2. 플로이드-워셜 (Floyd-Warshall)
다익스트라가 단일 출발점 최단 거리라면, 플로이드-워셜은 모든 정점 쌍의 최단 거리를 한 번에 구한다.
특징:
- 음의 가중치도 가능 (음의 사이클만 없으면 됨)
- 시간복잡도 O(V³)
- 코드가 매우 단순
핵심 아이디어: "k를 경유지로 거치면 더 짧아지는가?"
map[i][j] = min(map[i][j], map[i][k] + map[k][j])final int MAX = Integer.MAX_VALUE >> 2; // MAX_VALUE 그대로 쓰면 더할 때 오버플로우
// 연결 안 된 간선은 MAX로 초기화
if (i != j && map[i][j] == 0) map[i][j] = MAX;
// 경유지 k를 바깥 루프로
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] > map[i][k] + map[k][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}Integer.MAX_VALUE >> 2를 쓰는 이유: MAX_VALUE 그대로 쓰면 더할 때 int 범위를 넘어서 음수가 된다. 절반 이하로 줄여서 안전하게 사용한다.
경유지 k가 가장 바깥 루프여야 한다. k가 안쪽이면 아직 k를 거친 경로가 완성되지 않은 상태에서 비교하게 되어 틀린 결과가 나온다.
다익스트라 vs 플로이드-워셜
| 다익스트라 | 플로이드-워셜 | |
|---|---|---|
| 출발점 | 단일 | 모든 쌍 |
| 음의 가중치 | 불가 | 가능 (음의 사이클 없을 때) |
| 시간복잡도 | O(ElogV) | O(V³) |
| 코드 복잡도 | 복잡 | 단순 (3중 for문) |
정점이 적고 모든 쌍의 거리가 필요하면 플로이드-워셜이 편하다.
3. BOJ 17143 - 낚시왕 (시뮬레이션)
낚시왕이 매 초 한 칸씩 오른쪽으로 이동하면서 가장 위에 있는 상어를 잡고, 나머지 상어는 이동한 후 같은 칸에 있으면 큰 상어가 작은 상어를 먹는 문제다.
핵심 구현 포인트:
상어 이동 최적화 - 모듈러 연산
상어 속도가 최대 1000이고 낚시왕이 최대 100칸 이동하므로 단순 시뮬레이션은 9억 번 연산이 필요하다.
// 상하 이동: 반복 주기 = (R-1) * 2
s = s % (R * 2 - 2);
// 좌우 이동: 반복 주기 = (C-1) * 2
s = s % (C * 2 - 2);경계에서 튕기는 이동은 이 주기로 나눈 나머지만 실제로 시뮬레이션하면 된다.
두 가지 구현 방식
내 풀이 (List + Map 동시 관리):
ArrayList<Shark>로 상어 목록 관리Shark[][]map으로 위치 관리- 이동 후 killShark()에서 같은 위치의 상어 중 큰 것만 남김
김승훈 풀이 (old/new 배열 분리):
oldField에서 읽고newField에 결과 저장- 수식으로 경계 튕김 처리:
curY = 2*R - 2 - curY - 더 계산 중심적인 접근
4. BOJ 1062 - 가르침 (BackTracking + BitMask)
남극 언어의 단어는 모두 "anta"로 시작하고 "tica"로 끝난다. a, c, i, n, t 5개는 기본으로 배워야 하고, K개의 글자를 배울 때 읽을 수 있는 단어의 최대 수를 구하는 문제다.
버전 1 - boolean 배열 (Main_1062)
static boolean[] letters = new boolean[26];
// a, c, i, n, t는 기본으로 true
letters['a'-'a'] = true;
letters['c'-'a'] = true;
letters['i'-'a'] = true;
letters['n'-'a'] = true;
letters['t'-'a'] = true;
private static void combi(int c, int cnt) {
if (cnt == K) { check(); return; }
if (c > 'z') return;
combi(c+1, cnt); // c를 안 배우는 경우
if (!letters[c-'a']) { // 아직 안 배운 문자면
letters[c-'a'] = true;
combi(c+1, cnt+1);
letters[c-'a'] = false;
}
}버전 2 - BitMask (Main_1062_2)
단어와 배운 글자를 int 하나로 표현해서 비교를 & 연산 하나로 끝낸다.
static int letters; // 배운 글자를 비트로 표현
letters |= 1 << 'a'-'a';
// ... a,c,i,n,t 세팅
// 단어도 비트로 저장 (anta/tica 부분 제외하고 중간 글자만)
for (int j = 4; j < len-4; j++) {
bword |= (1 << (word.charAt(j)-'a'));
}
words[i] = bword;
// 체크: 배운 글자로 단어의 모든 글자를 커버하는지
if ((mask & word) == word) count++; // word의 모든 비트가 mask에 있으면 읽을 수 있음(mask & word) == word가 핵심이다. word에 필요한 글자가 mask에 모두 있으면 두 값이 같아진다.
5. BOJ 14503 - 로봇청소기 (시뮬레이션 + 재귀)
방향 전환 로직이 핵심이다.
북(0) → 동(1) → 남(2) → 서(3)
왼쪽(반시계): d = (d + 3) % 4 (= d - 1, 0이면 3으로)
후진: d = (d + 2) % 4public static void clean(int r, int c, int d) {
// 1. 현재 위치 청소
if (map[r][c] == 0) { map[r][c] = 2; cnt++; }
// 2. 왼쪽부터 4방향 확인
int origin = d;
for (int i = 0; i < 4; i++) {
d = (d + 3) % 4; // 반시계 회전
int nr = r + dr[d], nc = c + dc[d];
if (map[nr][nc] == 0) { // 청소 안 된 공간
clean(nr, nc, d);
return;
}
}
// 3. 4방향 모두 불가능하면 후진
int nd = (origin + 2) % 4;
int nr = r + dr[nd], nc = c + dc[nd];
if (map[nr][nc] != 1) { // 벽이 아니면 후진
clean(nr, nc, origin); // 방향은 유지한 채 후진
}
}맵의 사방이 벽으로 둘러싸여 있어서 경계 검사가 필요 없다는 것도 포인트다. 문제에서 주어지는 맵 자체가 패딩 역할을 한다.
6. 리뷰
오늘 낚시왕 문제에서 모듈러 최적화가 인상 깊었다. 경계에서 튕기는 이동은 (R-1)*2 주기로 반복된다. 속도 1000인 상어가 5칸짜리 행에서 이동하면 1000 % 8 = 0, 즉 원래 자리다. 이걸 1000번 반복하는 대신 한 번 나눗셈으로 끝낸다.
가르침 문제의 두 버전 비교도 흥미로웠다. boolean 배열 버전은 이해하기 쉽고, BitMask 버전은 단어 비교를 (mask & word) == word 한 줄로 끝낸다. 코드 길이는 비슷한데 체크 로직이 극적으로 단순해졌다.
시뮬레이션 문제는 구현 자체보다 방향 전환 수식 (d+3)%4, (d+2)%4 같은 수학적 표현을 깔끔하게 잡는 게 핵심이다.
7. 키워드 정리
플로이드-워셜
8. 내일의 목표
- 면접준비
- ADsP2단원
- DB공부시작
