교차로신호제어는 원본 자료에 문제 정의와 grader 구조체(TrafficSignal·Coordinates)만 공개돼 있고 검증된 통과 코드가 없다. 따라서 이 페이지는 다른 심층분석과 달리 — 라인 단위 코드 해부 대신, 시뮬레이션 + 탐욕적 신호 스케줄링 관점에서 베스트 해법을 설계하고 그 정당성을 논증한다. 코드는 의사코드와 핵심 부분의 C++ 스케치로 제시하며, 추측이 들어가는 곳은 "설계 제안"임을 명시한다.
먼저 원본 자료가 확실히 알려주는 것과, 우리가 설계로 메워야 하는 것을 엄격히 구분한다. 정직함이 이 페이지의 출발점이다.
MAXN × MAXM = 1000 × 1000 격자다.ROAD_CNT = 100개. TC는 MAX_TC = 10개.struct Coordinates { int y, x; } — 격자 좌표.struct TrafficSignal { int signal, next_signal; } — 각 교차로(신호)는 현재 상태 signal과 다음 사이클 상태 next_signal 두 필드를 가진다.TrafficSignal이 signal과 next_signal을 분리해 가진다는 사실은 강력한 단서다. 이것은 동기식(synchronous) 갱신 모델의 표준 형태다 — 셀룰러 오토마타가 모든 셀의 다음 상태를 먼저 계산한 뒤 일제히 전환하는 것과 같다. 만약 갱신이 비동기였다면 필드 하나면 충분했을 것이다. 두 필드의 존재는 곧 "모든 교차로가 next_signal을 계산해 두고, 사이클 경계에서 동시에 signal ← next_signal"이라는 절차를 강하게 시사한다.
signal / next_signal의 쌍은 "현재로 시뮬레이션, 다음을 미리 계산, 경계에서 일괄 전환"이라는 동기식 루프를 거의 지정하다시피 한다. 베스트 해법의 골격은 추측이 아니라 이 구조적 단서에서 연역된다.
이로써 베스트 해법의 골격이 세 부분으로 정해진다.
signal[]로 도로 위 차량 흐름을 한 스텝 전진시킨다.next_signal[]을, "현재 가장 정체된 흐름을 가장 빨리 풀어주는" 방향으로 결정한다.signal ← next_signal을 동시에 적용한다.이 세 부분은 로봇청소기(№ 01)의 분해 원리와 같은 정신을 따른다 — 흐름을 전진시키는 일(시뮬레이션)과 신호를 정하는 일(스케줄링)을 독립된 관심사로 분리하면, 각각을 따로 최적화할 수 있다.
점수의 정확한 공식은 자료에 없다. 그러나 PENALTY가 10¹³이고 문제 이름이 "신호제어"라는 점, 그리고 grader가 도로별 흐름을 추적한다는 구조에서 — 점수는 누적 정체 비용(혼잡), 즉 "신호 대기로 멈춰 있는 차량·시간의 총합"이라고 보는 것이 가장 합리적인 모델이다. 이 가정 위에서 설계를 논증한다.
매 사이클 경계에서 다음이 성립하도록 설계한다: 모든 교차로 i에 대해 signal[i] ← next_signal[i]가 동시에 적용되고, 그 사이 어떤 교차로도 갱신된 이웃의 신호를 미리 읽지 않는다.
이 불변식이 깨지면 — 즉 교차로 A가 갱신된 뒤 교차로 B가 A의 새 신호를 보고 자기 결정을 내리면 — 같은 사이클 안에서 갱신 순서에 따라 결과가 달라진다. next_signal을 모두 계산한 뒤에 일괄 전환하는 두 단계 분리가 이 순서 의존성을 제거한다.
각 사이클에서, "현재 가장 혼잡한 흐름 방향에 녹색을 우선 배정"하는 탐욕적 규칙은 그 사이클의 정체 증가분을 최소화하는 방향으로 작동한다. 전역 최적은 아니나, 사이클별 국소 최선의 누적은 PENALTY를 회피하고 경쟁력 있는 점수를 만든다.
한 교차로에서 충돌하는 두 흐름 방향 N-S와 E-W를 생각하자. 한 사이클에 한 방향만 녹색이 될 수 있다(동시 녹색은 충돌). N-S에 대기 차량 qNS, E-W에 qEW가 있고 qNS > qEW라 하자.
N-S에 녹색을 주면 이 사이클에 멈춰 기다리는 차량은 qEW, 반대로 하면 qNS다. 정체 비용이 대기 차량 수에 비례하므로, qNS > qEW일 때 N-S 녹색이 이 사이클의 대기 비용을 더 작게 만든다(qEW < qNS).
즉, 어떤 스케줄에서 더 혼잡한 쪽을 멈춰 세웠다면, 그 사이클의 두 방향 결정을 맞바꿔 항상 비용을 줄이거나 같게 만들 수 있다 — 표준 교환 논법이다. 사이클마다 이 국소 결정을 반복하면 정체가 통제된다. 단, 미래 사이클의 흐름 변화까지 내다보지는 못하므로 이는 국소 타당성이며, §4의 그린 웨이브가 그 한계를 보완한다.
풀이 코드가 없으므로 핵심 골격은 의사코드로 제시한다 — 다른 심층분석과 달리 여기서는 코드 비중을 줄이고 설계 논증에 무게를 둔다. signal/next_signal 두 필드를 쓰는 동기식 루프의 표준형이다.
// 베스트 해법 골격 — 동기식 시뮬레이션 + 탐욕 스케줄러
for cycle in 0 .. T:
// (1) 시뮬레이션: 현재 signal[]로 흐름 한 스텝 전진
advance_traffic(signal[], queues[])
// (2) 스케줄링: 다음 사이클 신호를 탐욕적으로 결정
for each intersection i:
priority_NS = queue_NS[i] + age_NS[i] // aging 가중
priority_EW = queue_EW[i] + age_EW[i]
next_signal[i] = (priority_NS >= priority_EW) ? GREEN_NS : GREEN_EW
// (3) 동기식 전환: 모든 교차로 동시에
for each intersection i:
signal[i] = next_signal[i]
핵심은 (2)의 우선도 계산이다. 단순 대기열 길이만 보면 §2의 굶주림 함정에 빠지므로, 대기 시간 aging을 더한다. 아래는 우선도 계산 부분만 C++로 스케치한 것이다. 설계 제안 — 실제 grader API에 맞춰 필드명은 조정이 필요하다.
// 한 사이클의 next_signal 결정 — 탐욕 + agingvoid scheduleNext(TrafficSignal sig[], int n) { for (int i = 0; i < n; ++i) { int pNS = qNS[i] + ageNS[i] * AGE_W; // 대기열 + 누적대기·가중 int pEW = qEW[i] + ageEW[i] * AGE_W; if (pNS >= pEW) { sig[i].next_signal = GREEN_NS; ageNS[i] = 0; // 녹색 받은 쪽은 나이 리셋 ageEW[i] += 1; // 멈춘 쪽은 나이 누적 } else { sig[i].next_signal = GREEN_EW; ageEW[i] = 0; ageNS[i] += 1; } } // 동기식 전환은 별도 루프에서 일괄 적용 for (int i = 0; i < n; ++i) sig[i].signal = sig[i].next_signal;}
next_signal만 쓰고 signal은 읽기만 한다 — 어떤 교차로도 이웃의 갱신된 신호를 미리 보지 않는다. 둘째 루프가 일괄 전환을 수행한다. AGE_W는 굶주림 방지 강도를 조절하는 튜닝 파라미터로, 크면 공정하지만 순간 혼잡 대응이 둔해지고 작으면 그 반대다 — 10 TC에 대해 실험적으로 정한다.
시뮬레이션 부분 advance_traffic은 grader가 흐름을 어떻게 모델링하는지에 의존하므로 의사코드 수준으로 둔다 — 녹색 방향의 대기열에서 통과 용량만큼 차량을 빼고, 적색 방향 대기열에 유입 차량을 더하는 큐 갱신이 표준형이다.
스케줄러는 교차로 수에 선형이다 — 도로 100개가 만드는 교차로 수를 I라 하면 사이클당 O(I). 시뮬레이션도 도로별 큐 갱신이 O(ROAD\_CNT) = O(100). 총 사이클 수를 T라 하면 한 TC가 O(T·(I + 100)), 10 TC를 합쳐도 — I와 T가 수천 수준이라면 ~10⁷ 연산으로 시간 안에 든다. 1000×1000 격자 전체를 매 사이클 순회하지 않는다는 점이 중요하다 — 도로와 교차로만 추적한다.
§2의 탐욕 스케줄러는 한 사이클의 시야만 가진다. 그러나 도로망은 공간적으로 연결돼 있다 — 한 교차로를 통과한 차량은 다음 사이클에 이웃 교차로의 대기열로 흘러든다. 순수 탐욕은 이 공간적 전파를 내다보지 못한다.
그린 웨이브(green wave)는 이 한계를 보완하는 설계다. 같은 방향으로 흐르는 도로 묶음의 신호를 도미노처럼 순차 점멸시킨다 — 첫 교차로가 녹색일 때 출발한 차량 무리가, 다음 교차로에 도착할 즈음 그 교차로도 녹색이 되도록 위상(phase)을 어긋나게 배치한다.
그린 웨이브 위상식이 성립하면 다음이 보장된다: 한 교차로에서 녹색에 출발한 차량 무리는, 다음 교차로에 도착하는 순간 그 교차로도 녹색 상태다.
결과적으로 차량 무리는 멈추지 않고 도로 묶음 전체를 통과한다 — 정체 비용이 거의 0으로 수렴하는 흐름. 동기식 갱신("모두 동시에 전환")으로 만들어진 결과가 공간적으로는 파동으로 나타나는 것이 이 설계의 묘미다.
실전 설계는 두 전략을 혼합한다. 평상시 흐름이 균질한 도로 묶음에는 그린 웨이브 위상을 고정 배치해 무정차 통과를 만들고, 국소적으로 비대칭 혼잡이 감지된 교차로에서는 §2의 탐욕 + aging이 위상을 일시 무시하고 개입한다. 그린 웨이브가 구조적 효율을, 탐욕 스케줄러가 국소 적응을 담당하는 분업이다.
| 전략 | 제약 회피 | 정체 경향 | 구현 | 평가 |
|---|---|---|---|---|
| 고정 주기 (모든 신호 동일 위상) | 보장 | 높음 | 쉬움 | 흐름의 공간 전파를 무시 — 매 교차로마다 정차 |
| 순수 탐욕 (혼잡한 쪽 우선) | 위험 | 중간 | 쉬움 | 한 사이클 시야만 — 굶주림으로 PENALTY 위험 |
| 그린 웨이브만 (고정 위상 파동) | 보장 | 낮음(균질 흐름) | 중간 | 균질 흐름엔 강하나 국소 비대칭 혼잡에 둔감 |
| 그린 웨이브 + 탐욕 aging 혼합 | 보장 | 낮음 | 중간 | 구조적 효율(파동) + 국소 적응(탐욕)의 분업 |
표는 설계 비교다 — 측정된 점수가 아니라 각 전략이 정체 비용에 어떻게 작용하는지를 정리한다. 고정 주기는 구현이 가장 쉽지만 흐름의 공간 전파를 통째로 무시해 모든 교차로에서 정차가 발생한다. 순수 탐욕은 §2의 굶주림 함정 때문에 제약 위반(PENALTY) 위험을 안는다. 그린 웨이브 단독은 균질 흐름에 강하지만 한 도로만 갑자기 붐비는 국소 비대칭에 둔감하다. 따라서 — 그린 웨이브로 구조적 무정차 효율을 깔고, 탐욕 + aging으로 국소 혼잡에 적응하는 혼합 설계가 §2 Theorem(국소 타당성)과 §4 Invariant(파동 정합)를 모두 만족하는 최선의 후보다.
next_signal 계산과 signal 전환을 같은 루프에 섞으면, 먼저 갱신된 교차로의 새 신호를 뒤 교차로가 읽어 — 갱신 순서에 따라 결과가 달라진다. §2 Invariant대로 반드시 두 루프로 분리하라.
(c.x + cycle) mod k의 부호나 mod 값을 틀리면 파동이 차량 진행 방향과 어긋나 — 무정차는커녕 매 교차로에서 적색을 만난다. 작은 격자(예: 3×3)로 손검증하라.
05·06번과 달리 이 페이지는 측정된 SCORE를 제시할 수 없다. 검증된 통과 코드가 없기 때문이다. 정직한 검증 기준은 다음과 같다 — 점수가 아니라 설계가 자료에서 확정된 제약과 모순되지 않는가이다.
TrafficSignal 구조와 일반적 신호제어 원리로부터 베스트 해법을 설계하고 그 정당성을 논증한 것이다. "동기식 시뮬레이션 + 탐욕 aging 스케줄러 + 그린 웨이브 혼합"이라는 골격은 자료의 확정 사실(signal/next_signal 분리, 동기식 갱신 시사)에서 연역되었고, 위상식·가중치 같은 구체 수치는 점수 공식과 흐름 모델이 공개되면 재튜닝되어야 할 설계 제안이다. 이 페이지의 가치는 정답 코드가 아니라 — "이런 자료 구조 앞에서 어떤 종류의 해법을, 어떤 근거로 설계해야 하는가"라는 사고의 골격에 있다.