[SK플래닛] ASAC 빅데이터전문가 11기 | 08일차

오늘은 탐색 문제를 풀면서

단순히 DFS, BFS를 외우는 것보다

문제를 어떤 구조로 바꿔서 볼지, 그리고 그걸 어떤 코드 형태로 구현할지를 더 많이 고민한 날이었다.

특히 오늘은 이런 흐름이 계속 이어졌다.

• BFS에서는 왜 리스트 대신 deque를 써야 하는지
• K거리 도시 문제에서 왜 DFS가 아니라 BFS인지
• 미로 탐색에서는 왜 도시 번호가 아니라 좌표로 생각해야 하는지
• 얼음 문제에서는 왜 탐색을 한 번 더 “포장”해야 하는지

오늘은 정답만 보는 날이 아니라,

기존에 배운 탐색 아이디어를 문제에 맞게 튜닝하는 연습을 한 느낌이 더 강했다.

---

1. deque: BFS에서 왜 중요한지 다시 정리

오늘 제일 먼저 정리한 건 deque였다.

메모에도 적어둔 것처럼 deque는 double ended queue다.

from collections import deque

q = deque()

q.append(10)       # 오른쪽 추가
q.appendleft(5)    # 왼쪽 추가

print(q)           # deque([5, 10])

print(q.popleft()) # 왼쪽에서 꺼내기
print(q.pop())     # 오른쪽에서 꺼내기

핵심은 이거였다.

• append left
• append
• pop left
• pop

즉, 양쪽 끝을 다 빠르게 다룰 수 있는 구조라는 점이다.

오늘 정리한 텍스트에서도

파이썬에서 BFS를 구현할 때 리스트의 pop(0)은 비효율적이고,

앞에서 꺼내는 작업이 많은 BFS에서는 collections.deque를 쓰는 게 자연스럽다고 설명돼 있었다. 특히 deque는 양쪽 끝을 뚫어 둔 구조라 앞쪽 제거가 빠르다는 점이 강조돼 있었다.

예전에는 그냥

“큐니까 리스트 써도 되지 않나?”

싶었던 적도 있었는데,

오늘은 이게 단순 문법 차이가 아니라 자료구조 선택 문제라는 게 더 잘 들어왔다.

리스트로도 이렇게는 쓸 수 있다.

q = []
q.append(1)
q.append(2)
q.append(3)

print(q.pop(0))

그런데 BFS는 앞에서 계속 꺼내야 하니까

문제가 커지면 이 방식이 점점 부담이 된다.

💡 그래서 오늘 남은 건 아주 단순했다.

BFS를 파이썬으로 구현할 때는, 큐를 “deque”로 생각하는 게 거의 기본이다.

---

2. K거리 도시: 왜 이 문제는 BFS인가

🔗 문제 링크

백준 18352 - 특정 거리의 도시 찾기

오늘 K거리 도시 문제는

처음부터 “이건 BFS인가 DFS인가”를 생각하게 했던 문제였다.

정리된 텍스트에서도

이 문제는 모든 도로의 거리가 1이라는 점이 핵심이고,

이런 경우 출발점에서부터 점진적으로 퍼져 나가는 BFS가 최단거리 추적에 더 적합하다고 설명돼 있었다. DFS는 왔다 갔다 하며 깊게 들어가기 때문에 거리 추적이 상대적으로 불편하지만, BFS는 레벨 단위로 진행되기 때문에 이런 문제와 잘 맞는다는 흐름이었다.

즉, 오늘 이 문제를 보면서 다시 정리된 건 이거였다.

• 이 문제는 거리 문제가 맞다
• 그런데 모든 간선 가중치가 동일하다
• 그러면 BFS의 레벨 순회가 최단거리 개념과 자연스럽게 연결된다

이게 오늘 꽤 중요했다.

예전에는 탐색 문제를 보면

“DFS도 되나? BFS도 되나?”

정도로만 생각했는데,

오늘은 적어도

최단거리 + 모든 간선 길이 1

이 조합이 나오면 BFS를 먼저 떠올리는 게 맞겠다고 느꼈다.

---

3. K거리 도시: 내가 처음 세운 아이디어

처음에는 대략 이런 식으로 접근했다.

# 일단 ? BFS로 진행
# 입력을 받는건 도시개수N, 도로개수 M, 거리정보 K, 출발도시번호 X =>def(N,M,K,X)

# 처음에 도시 세팅 -> 인접 리스트 길이 N
# 거리 정보를 넣어줘야함 K 넣기 -> for문으로 거리 정보 넣기 -> 0번은 도시, 1번 연최조결된거 -> 0번을 기준으로 1번을 리스트 요소에 추가

# 한일 리스트
# 출발점에서 할일 방문 할일 추가 -> 바로 가면 흠 1인거고 , 들려서 가면 그거만큼 추가 인데

# 아 pop이 되면 +1 추가
# 근데 이제 반복할때마다 +1 추가하고, 최종 pop(0)에서는 그걸 반영해서 dep 추가 !

# 흠 dep가 k와 같다면
# 그 리스트의 번호를 출력하면 될듯 ?
# 업ㅅ으면 -1출력

지금 다시 보면,

방향 자체는 아주 엉뚱하지 않았다.

적어도

• 이건 BFS 쪽이다
• 인접 리스트를 써야 한다
• 거리 기록이 필요하다

여기까지는 맞게 보고 있었다.

그런데 구현으로 들어가면서

“거리”를 정확히 어떻게 기록할지,

방문 여부와 거리를 어떤 식으로 함께 관리할지를 잘 못 잡았다.

---

4. K거리 도시: 처음 코드와 문제점

내 첫 코드는 이런 느낌이었다.

n,m,k,x = map(int,input("도시수 도로수 기준거리 출발도시 : ").split())

graph=[[]for i in range(n+1)]

for i in range(m):
  s,e = map(int,input("출발도시 도착도시 : ").split())
  graph[s].append(e)
graph

dis = [f'inf({i})' for i in range(n)] #길이
todo =[]
did = []

todo.append(x)

while todo:
  now = todo.pop(0)

  if dis[now]!=now:
    did.append(now)
    todo.extend(graph[now])
    dis[now]=now+1

print(did)

지금 다시 보면 꼬인 부분이 꽤 선명하다.

⚠️ 1) 거리 배열이 문자열이었다

dis = [f'inf({i})' for i in range(n)]

거리 배열은 숫자로 비교하고 갱신해야 하는데,

문자열처럼 만들어버려서 구조 자체가 어색해졌다.

거리 배열은 결국

• 아직 방문하지 않았는지
• 현재까지 최단거리가 얼마인지

를 저장해야 하므로 숫자 기반이어야 했다.

---

⚠️ 2) 리스트의 pop(0)을 그대로 썼다

now = todo.pop(0)

오늘 deque를 따로 정리한 이유가 이거였다.

BFS에서 앞에서 계속 꺼내는 작업이 필요하니까,

이건 deque.popleft()로 가는 게 맞았다.

텍스트에서도 리스트보다 deque가 BFS에 적합하다고 분명히 설명돼 있었다.

---

⚠️ 3) 거리 갱신 방식이 틀렸다

dis[now] = now + 1

이건 지금 보면

도시 번호에 1을 더한 것뿐이다.

문제에서 필요한 건

도시 번호가 아니라 거리였다.

즉, 다음 도시 nxt의 거리는

현재 도시 now의 거리에서 1을 더한 값이어야 했다.

distance[nxt] = distance[now] + 1

---

⚠️ 4) 방문 여부와 거리 관리를 따로따로 생각했다

처음에는 did 리스트도 따로 두고,

거리 배열도 따로 두고,

큐도 따로 두고 하다 보니 구조가 오히려 헷갈렸다.

그런데 오늘 정리된 흐름에서는

이 문제의 distance 배열이 단순한 방문 여부 기록이 아니라

정답지 자체처럼 쓰인다는 점이 중요했다.

즉, 방문했는지 확인하는 용도와, 최단거리를 저장하는 용도를 같이 맡는 구조였다.

---

5. K거리 도시: 오늘 정리한 정답 구조

오늘 정리한 최종 구조는 이쪽이었다.

• 인접 리스트로 그래프 만들기
• distance 배열을 1로 초기화
• 출발점 x의 거리만 0으로 설정
• BFS 진행
• 아직 방문하지 않은 도시만 큐에 넣고 거리 갱신
• 마지막에 거리 k인 도시만 출력

코드로는 이렇게 정리할 수 있었다.

from collections import deque

n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

distance = [-1] * (n + 1)
distance[x] = 0

q = deque([x])

while q:
    now = q.popleft()

    for nxt in graph[now]:
        if distance[nxt] == -1:
            distance[nxt] = distance[now] + 1
            q.append(nxt)

result = []
for city in range(1, n + 1):
    if distance[city] == k:
        result.append(city)

if result:
    for city in result:
        print(city)
else:
    print(-1)

이 문제를 통해 오늘 남은 핵심은 이거였다.

💡 BFS는 단순히 큐를 쓰는 문제가 아니라,distance 배열까지 같이 설계해서 “방문 + 최단거리”를 함께 관리하는 문제다.

---

6. 미로 탐색: 이번엔 도시 번호가 아니라 좌표였다

🔗 문제 링크

백준 2178 - 미로 탐색

미로 탐색은 앞 문제랑 같은 BFS 계열인데,

문제를 보는 단위가 완전히 달랐다.

K거리 도시는

노드 = 도시 번호였다.

그런데 미로 탐색은

노드 = 좌표 (x, y) 였다.

정리한 텍스트에서도

이 문제는 도시 번호가 아니라 “칸의 위치”가 중요하고,

따라서 큐에도 번호 하나가 아니라 좌표 두 개를 묶어서 넣어야 한다고 설명돼 있었다.

또 상하좌우 이동을 위해 dx, dy 같은 방향 벡터를 쓰는 구조가 핵심이라고 정리돼 있었다.

즉, 오늘 여기서 가장 중요했던 건

알고리즘 이름보다 노드를 무엇으로 볼 것인가였다.

• 그래프 문제 → 도시 번호
• 격자 문제 → 좌표
• 미로 문제 → 좌표 + 상하좌우 인접

이걸 문제마다 먼저 바꿔서 볼 수 있어야 했다.

---

7. 미로 탐색: 좌표형 BFS 코드로 정리

이 문제에서는 입력부터 격자를 2차원 리스트로 받아야 했다.

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

q = deque()
q.append((0, 0))

while q:
    x, y = q.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue

        if graph[nx][ny] == 0:
            continue

        if graph[nx][ny] == 1:
            graph[nx][ny] = graph[x][y] + 1
            q.append((nx, ny))

print(graph[n - 1][m - 1])

여기서 오늘 크게 남은 건 두 가지였다.

1) 큐에 (x, y)를 넣는다

더 이상 도시 번호 하나가 아니라,

좌표 두 개가 하나의 위치 정보를 이룬다.

2) 지도 자체를 거리 기록용으로 쓸 수 있다

새 칸을 발견할 때마다

graph[nx][ny] = graph[x][y] + 1

이렇게 바로 값을 덮어쓰면서

거리까지 함께 기록한다.

즉, 이 문제에서는 별도의 distance 배열을 만들지 않고

지도를 그대로 재활용할 수도 있었다.

이게 K거리 도시랑 또 닮아 있었다.

• K거리 도시 → distance 배열 따로 둠
• 미로 탐색 → graph를 거리 기록용으로 활용

결국 같은 BFS라도

정답을 어디에 기록할지는 문제마다 달라질 수 있었다.

---

8. 얼음 얼려 먹기: 이번엔 탐색을 한 번 더 포장해야 했다

🔗 참고 링크

얼음 얼려 먹기 설명 참고 링크

오늘 얼음 문제는 진짜 인상적이었다.

앞에 있던 문제들은 비교적 출발점이 명확했다.

• K거리 도시 → 시작 도시 x
• 미로 탐색 → (0, 0)

그런데 얼음 문제는 그렇지 않았다.

출발점을 하나만 정해서 끝나는 문제가 아니었다.

정리된 텍스트에서도

이 문제는 기존 탐색을 그대로 쓰는 게 아니라,

격자 전체를 돌면서 모든 칸을 시작점 후보로 보고 탐색을 포장해야 한다고 설명돼 있었다.

또 이 문제는 거리 누적이 필요한 게 아니라

연결된 0들을 1로 바꾸는 식으로 흔적만 남기면 되기 때문에, DFS든 BFS든 크게 상관없다고 정리돼 있었다.

이게 오늘 제일 크게 남은 부분이었다.

얼음 문제에서 핵심적으로 달라진 점

• 모든 칸을 시작점 후보로 본다
• 값이 0인 칸에서만 탐색 시작 가능
• 연결된 0들을 전부 1로 뒤집는다
• 탐색 하나가 끝날 때마다 카운트 +1

즉, 이 문제는

탐색 알고리즘을 한 번 더 큰 반복문으로 감싸는 문제였다.

---

9. 얼음 문제: 내가 이해한 방식대로 정리한 DFS 코드

이 문제는 DFS로 정리하면 이런 식이었다.

n, m = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return False

    if graph[x][y] == 0:
        graph[x][y] = 1

        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)

        return True

    return False

result = 0

for i in range(n):
    for j in range(m):
        if dfs(i, j):
            result += 1

print(result)

이 코드가 왜 중요했냐면,

앞 문제들과 구조가 확실히 달랐기 때문이다.

앞 문제들과 다른 점

1) 출발점이 고정되지 않았다

그래서 전체 격자를 다 순회하면서

“여기서 시작 가능한가?”를 먼저 본다.

2) 거리를 누적할 필요가 없다

그냥 방문 흔적만 남기면 된다.

즉, 0을 1로 바꾸는 것으로 충분하다.

3) 탐색이 하나 끝날 때마다 카운트한다

한 번의 DFS가 얼음 한 덩어리를 끝까지 처리하므로

True를 리턴하면 결과를 +1 한다.

이 문제는 진짜로

“탐색을 포장한다”는 표현이 딱 맞았다.

---

10. 오늘 느낀 점

오늘은 탐색 문제를 보면서

이제 조금씩 이런 기준이 생기는 것 같다.

1) 탐색 문제는 DFS/BFS를 고르는 것부터가 아니다

먼저 이걸 생각해야 한다.

• 노드는 무엇인가?
• 출발점은 하나인가, 여러 개인가?
• 거리까지 기록해야 하나?
• 방문 흔적만 남기면 되나?

2) BFS는 거리 / 레벨 / 최단거리와 잘 연결된다

K거리 도시가 딱 그랬다.

모든 간선 길이가 1이면 BFS의 레벨 순회가 곧 최단거리 개념이 된다.

3) 격자 문제는 좌표 문제로 바뀐다

미로 탐색은 결국

번호 탐색이 아니라 좌표 탐색이었다.

4) 어떤 문제는 탐색을 한 번 더 포장해야 한다

얼음 문제는

탐색 하나로 끝나는 게 아니라,

모든 칸에 대해 탐색 시작 여부를 판단해야 했다.

결국 오늘 세 문제를 관통한 핵심은 이거였다.

💡 탐색은 DFS/BFS를 외우는 게 아니라,문제를 그 알고리즘으로 표현 가능한 구조로 바꾸는 연습이다.

그리고 개인적으로 오늘 제일 크게 남은 건 이것도 있었다.

처음 코드가 틀렸다고 해서 문제를 완전히 못 읽은 건 아닐 수 있다.

K거리 도시처럼 방향은 맞았는데,

거리 배열 설계나 자료구조 선택이 틀어져서 무너지는 경우도 많다.

이런 날이 오히려 더 오래 남는다.

탐색은 DFS, BFS를 외우는 게 아니라, 문제를 그 방식으로 바꿔서 구현하는 연습에 가깝다.