앳코더 ABC 453 후기
tkd0711 · 2026. 4. 11.
AtCoder Beginner Contest 453
https://atcoder.jp/contests/abc453
- 날짜: 2026-04-11 (Sat)
- 결과: A~D AC (1025점)
- A: 2:29
- B: 6:31
- C: 13:45
- D: 80:43, 1트
1. 전체 느낌
이번 대회는 결과만 보면 꽤 만족스러웠다.
A, B를 무난하게 처리했고,
C도 빠르게 정리했다.
무엇보다 D를 결국 풀었다는 점이 가장 크다.
시간은 오래 걸렸지만,
한 번 방향을 잡은 뒤 원트로 마무리했다는 점에서 의미가 있었다.
즉 이번 대회는
- C까지는 꽤 깔끔했고
- D에서 오래 고민했지만
- 끝까지 밀어붙여서 AC한 대회
였다.
2. A, B – 안정적인 시작
A와 B는 큰 문제 없이 해결했다.
최근처럼 초반 문제는 비교적 안정적으로 풀리고 있고,
이번에도 A/B에서 크게 흔들리지 않았다.
ABC에서 중요한 건
초반 문제를 빠르게 넘기고 C, D에 사고 시간을 확보하는 건데,
이번에는 그 흐름이 잘 나왔다.
3. C – 완전탐색으로 바로 내려온 판단이 좋았음
문제 요약
시작 위치가 0.5이고,
총 N번 이동하면서 매번 왼쪽 또는 오른쪽으로 L_i만큼 움직인다.
이때 좌표 0을 지나는 횟수의 최댓값을 구하는 문제였다.
제한은 N ≤ 20이었다.
접근
문제를 보자마자 핵심은 바로 보였다.
- 매 이동마다 선택지는 2개
N ≤ 20- 그럼 경우의 수는
2^N
즉 완전탐색이 가능했다.
그래서 DFS로
- 현재 몇 번째 이동인지
- 현재 위치가 어디인지
- 지금까지 0을 지난 횟수가 몇 번인지
를 상태로 두고 전부 탐색했다.
구현
현재 위치를 x로 두고,
- 왼쪽으로 가는 경우
- 오른쪽으로 가는 경우
두 갈래를 전부 DFS로 내려가면서
0을 지나는 순간만 카운트했다.
문제에서
“좌표 0에서 끝나는 이동은 없다”고 보장되어 있어서,
부호만 비교해도 충분했다.
느낀 점
이 문제는 사실상
제한을 보고 바로 완전탐색으로 내려올 수 있느냐가 핵심이었다.
복잡한 DP나 수학으로 볼 필요 없이,N ≤ 20이라는 제약을 보고 2^N이 가능하다는 판단을 빨리 한 게 좋았다.
조금 더 깔끔하게 하려면
시작점을 0.5 대신 전체를 2배 해서 정수로 처리하는 방법도 있었겠지만,
이번 구현도 충분히 맞는 방향이었다.
4. D – 상태 설계는 맞았고, 구현을 끝까지 밀어붙여서 AC
문제 요약
격자에서 상하좌우로 이동하는데,
칸의 종류에 따라 다음 이동 방향 제약이 달라진다.
.: 자유 이동o: 직전 방향과 같은 방향으로만 이동x: 직전 방향과 같은 방향으로는 이동 불가#: 벽S,G: 시작점과 도착점
도달 가능 여부를 판별하고,
가능하면 실제 경로를 출력하는 문제였다.
처음 생각한 핵심
처음 문제를 읽고 제일 먼저 든 생각은 이거였다.
- 단순 2차원 방문으로는 안 된다
- 이전에 어떤 방향으로 왔는지가 중요하다
- 즉 상태는
(i, j, lastDir)이어야 한다
이 판단은 맞았다.
실제로 o, x 칸은
같은 칸이라도 “어느 방향으로 들어왔는지”에 따라 다음 이동 가능 여부가 달라지기 때문에,
3차원 방문 체크가 필요했다.
첫 구현과 TLE
처음에는 BFS 상태와 함께
경로 문자열 자체를 큐에 같이 넣는 식으로 구현했다.
즉 상태 하나마다 현재까지의 경로 문자열을 계속 들고 다니는 방식이었는데,
이건 상태 수가 많아지면 문자열 복사가 너무 많이 일어나서 무거울 수밖에 없었다.
그래서 여기서 TLE가 났고,
그 뒤에 “이걸 최적화하려면 역추적으로 가야겠다”는 생각으로 방향을 바꿨다.
정답 코드에서 바꾼 점
최종적으로는
- BFS에서는 상태만 관리하고
- 각 상태가 어디서 왔는지
parent - 어떤 문자로 들어왔는지
parr
를 따로 기록한 뒤,
도착점 G에 도달하면 부모를 따라가면서 역추적해서 경로를 복원했다.
즉 경로 문자열을 큐에 계속 넣는 대신,
그래프 탐색 + 부모 포인터 복원 형태로 바꾼 것이다.
이 판단이 맞았고,
결국 이 방식으로 AC가 났다.
아쉬웠던 점
아쉬운 점이 있다면 구현이 꽤 길어졌다는 것이다.
특히 o, x, ., S, G를 처리하는 전이 로직을
각각 if문으로 길게 분기해서 쓰다 보니 코드가 다소 무거워졌다.
대회 중에는 일단 AC가 중요하니까 그대로 밀어붙였지만,
나중에 다시 보면
- 방향 전이를 함수로 분리하거나
- 공통 로직을 정리하거나
- 방향 배열을 더 활용해서
좀 더 깔끔하게 정리할 수 있었을 것 같다.
그래도 좋았던 점
그럼에도 불구하고 이 문제에서 가장 의미 있었던 건:
- 상태 설계를 정확히 했고
- TLE 원인을 파악해서
- 문자열 누적 대신 역추적으로 최적화 방향을 바꿨고
- 결국 원트 AC로 마무리했다
는 점이다.
즉, 이 문제는 단순히 “운 좋게 맞춘 문제”라기보다
상태 설계 + 구현 최적화 + 복원까지 제대로 처리한 문제였다.
5. 이번 대회에서 좋았던 점
1) C를 빠르게 정리했다
제한을 보고 바로 완전탐색으로 내려온 판단이 좋았다.
2) D 상태 모델링을 맞췄다
(좌표, 이전 방향)이 상태라는 핵심을 정확히 봤다.
3) TLE 이후 구현 방향을 바꿨다
경로 문자열을 직접 들고 다니는 대신,
부모 배열로 역추적하는 방식으로 고친 게 결정적이었다.
4) D를 끝까지 풀었다
시간은 오래 걸렸지만,
결국 400점을 AC했다는 건 분명 큰 성과였다.
6. 아쉬웠던 점
이번 대회에서 아쉬운 점은 크게 두 가지였다.
1) D 구현이 길고 무거웠다
상태 설계는 맞았지만, 전이 로직이 길어져서 코드가 지저분해졌다.
2) D에서 시간을 많이 썼다
80분 넘게 사용했기 때문에,
만약 다음 단계 문제를 보려 했다면 시간적으로는 거의 불가능했다.
즉 이번 대회는
풀긴 풀었지만, 더 깔끔하고 더 빨리 풀 수 있었을 것 같은 문제가 D였다.
7. 다음 목표
- 방향 의존 상태가 있는 격자 문제에서
(좌표, 방향)상태를 더 자연스럽게 떠올리기 - BFS 경로 복원 문제에서는
문자열 누적 대신 parent 역추적을 우선 생각하기 - 구현이 길어질 때는
전이 함수로 분리해서 코드 가독성을 챙기기 - 맞는 아이디어를 잡았으면
그다음은 “더 빨리, 더 깔끔하게” 구현하는 연습하기
한 줄 정리
ABC 453은 C를 빠르게 처리하고, D를 오래 걸렸지만 끝까지 밀어붙여 AC한 대회였다.