SSAFY 알고리즘 과정의 배틀싸피는 격자 지도 위에서 탱크를 움직여 적 포탑을 부수는 대전형 과제입니다. 매 턴 서버가 지도와 상태를 보내 주면, 봇이 이동·발사 같은 명령 하나를 돌려줍니다. 통신 부분은 과정에서 제공하는 기본 코드를 그대로 쓰고, 저는 "이번 턴에 무엇을 할지"를 정하는 알고리즘 부분을 세 번에 걸쳐 고쳤습니다.
과정에서 제공한 기본 코드와 문제 명세는 공개하지 않고, 제가 바꾼 판단 로직만 정리합니다.
v0 — 처음 한 번만 길을 찾는 봇
기본 구조는 단순했습니다.
- 게임 시작 때 한 번, 내 위치(
M)에서 목표(X)까지 BFS로 최단 경로를 구한다 - 목표 바로 옆에 도착하면 그 방향으로 발사
- 이후 매 턴 경로에서 명령을 하나씩 꺼내 보낸다
문제는 지도가 바뀌어도 처음 계획을 계속 따른다는 점이었습니다. 적이 움직이거나 길이 막히면 엉뚱한 방향으로 계속 갔습니다.
v1 — 사거리와 장애물을 반영
BFS가 "목표 바로 옆"만 보던 것을 실제 규칙에 맞게 바꿨습니다.
- 사거리: 포탑은 직선으로 3칸 앞까지 쏠 수 있으므로, 각 칸에서 네 방향으로 1~3칸을 확인해 목표가 보이면 그 자리에서 발사
- 시야 막힘: 확인하다가 지나갈 수 없는 칸을 만나면 그 방향은 거기서 중단
- 이동 가능한 칸을 "벽이 아닌 칸"에서 "땅·모래처럼 실제로 갈 수 있는 칸"으로 좁힘
v2 — 매 턴 다시 판단하는 봇
여기서 구조를 크게 바꿨습니다. 매 턴 처음부터 다시 계획하고, 길찾기 앞에 "지금 무엇을 목표로 할지"를 정하는 단계를 넣었습니다.
매 턴:
내 탄약(일반·메가)과 목표 체력을 읽는다
탄이 부족한가? (일반탄 × 30 + 메가탄 × 70 < 목표 체력)
├─ 부족하고 보급시설 옆이면 → 보급 암호를 해독해 탄 받기
├─ 부족하면 → 목표를 '보급시설'로 바꾼다
└─ 충분하면 → 목표는 적 포탑
경로 찾기:
1차 BFS: 나무를 피해서
2차 BFS: 안 되면 나무를 쏘고 지나가는 경로 (쏘기 + 이동 2개 명령)
포탑을 맞히는 마지막 발사(또는 일반탄이 없을 때)에는 메가탄
예외가 나면 그 턴은 대기 — 봇이 죽지 않게
두 번 찾는 BFS
나무는 쏘면 없어지지만 한 턴이 더 듭니다. 처음부터 나무를 "비용이 큰 칸"으로 넣는 대신, 나무 없이 먼저 찾고 실패할 때만 나무를 뚫는 경로를 허용했습니다. 가중치를 다루는 알고리즘(다익스트라)으로 바꾸지 않고도, 대부분의 상황에서 원하는 우선순위를 얻을 수 있었습니다.
피드백으로 키를 찾는 암호 해독
보급시설에서 탄을 받으려면 문자를 일정 칸씩 밀어 쓴 암호(시저 암호)를 풀어야 합니다. 키를 미리 알 수 없어서, 해독 결과가 맞았는지를 다음 턴 상태로 확인했습니다.
- 해독을 보낸 뒤 메가탄 수가 그대로면 → 키가 틀렸다 → 다음 키로
- 메가탄이 늘었으면 → 그 키를 유지
정답을 모르는 상태에서 행동 → 결과 관찰 → 다음 시도를 반복하는 작은 탐색 루프입니다.
배운 것
- 계획을 한 번 세우고 따르는 구조는 환경이 바뀌면 깨집니다. 매 턴 다시 계산하는 비용보다, 낡은 계획을 따르는 비용이 훨씬 컸습니다.
- "어디로 갈지"보다 "무엇을 목표로 할지"가 먼저입니다. 길찾기는 그대로 두고 목표 선택 단계를 앞에 둔 것이 가장 큰 개선이었습니다.
- 실패해도 멈추지 않는 기본값(예외 시 대기)이 실전에서는 정확도만큼 중요했습니다.
모델 실험에서 "이번 제출이 직전보다 나은가"를 매번 다시 판단하던 것과 결국 같은 습관이었습니다.