구현 문제에서 '새 배열 교체' vs. '좌표 집합만 교체'

언제 '새 배열'을 만들고, 언제 '좌표 집합'만 쓸까?

이 두 방식을 구별하는 기준은 "데이터의 밀도"와 "참조 방식"에 있다.

A. 매 단계 '새 배열' 생성이 유리한 경우 (밀도가 높을 때)

• 상태 전파: 한 칸의 변화가 주변 칸에 연쇄적으로 영향을 줄 때 (예: 모래바람, 불 번지기, 물 시뮬레이션)
• 주변 참조: board[i][j]의 다음 값이 board[i-1][j], board[i+1][j] 등 주변 8칸의 모든 상태에 의존할 때
• 객체가 꽉 찼을 때: 보드의 거의 모든 칸에 데이터가 들어있어서 좌표만 따로 관리하는 게 더 메모리를 많이 먹을 때

B. '좌표 집합(Set/Dict)'만 관리해도 되는 경우 (밀도가 낮을 때)

• 독립적 이동: 객체들이 서로의 상태를 실시간으로 참조하지 않고, 각자 자기 갈 길을 갈 때 (예: 아두이노, 로봇, 총알)
• 희소 데이터(Sparse Data): 100*100 보드에 객체는 고작 10~20개뿐일 때. (10,000칸을 다 뒤지는 것보다 20개 좌표만 보는 게 훨씬 빠름)
• 충돌 판정 중심: 이동 후 "겹치면 삭제" 같은 로직이 핵심일 때 (딕셔너리가 보드보다 훨씬 유리함)

---

문제를 알아보는 결정적 힌트

다음에 문제를 볼 때 이 질문을 스스로에게 던져보기

"내가 지금 보드(board[i][j])의 '빈 공간(.)'을 연산에 쓰고 있는가?"

1. YES: 빈 공간이 물길이 되거나, 빈 공간의 개수를 세야 하거나, 주변 빈 공간으로 확산된다면 매번 새 배열을 만드는 게 편하다.
2. NO: 빈 공간은 그냥 배경일 뿐이고, 중요한 건 'I'와 'R'의 위치뿐이라면 좌표 관리가 훨씬 유리하다. 마지막에 출력할 때만 그 좌표들을 보드에 찍어주면 된다.

보드가 "출력용 도구"인지, "내부 로직을 계산하는 데 필수적인 데이터 구조"인지 파악해보자!