[백준] 21736번 : 헌내기는 친구가 필요해 [BFS 설명 有]

https://www.acmicpc.net/problem/21736

21736번: 헌내기는 친구가 필요해

 

 

 

 

 

 

 

 

import sys
from collections import deque
    



n, m = map(int, sys.stdin.readline().split(" "))
l = []
a,b = 0, 0
for i in range(n):
    l2 = list(sys.stdin.readline().strip())
    if 'I' in l2:
        a = i
        b = l2.index('I')
    l.append(l2)


d = deque([[a,b]])

direction = [[0,1], [1,0],[0,-1],[-1,0]]

ans = 0

while d:
    d2 = d.popleft()
    a,b = d2[0], d2[1]

    for dir in direction:
        if 0 <= a+dir[0] < n and 0<= b+dir[1] < m:
            if l[a+dir[0]][b+dir[1]] == "O":
                l[a+dir[0]][b+dir[1]] = "-1"
                d.append([a+dir[0], b+dir[1]])

            elif l[a+dir[0]][b+dir[1]] == "P":
                ans = ans+1
                l[a+dir[0]][b+dir[1]] = "-1"
                d.append([a+dir[0], b+dir[1]])


if ans == 0:
    print("TT")
else:
    print(ans)

 

 

 

 

 

이 문제도 간단한 DFS 문제이다.

 

 

도연이의 좌표를 찾은 다음, 그 좌표를 기준으로 dfs를 수행하면 된다.

 

 

P인 경우면 결과값에 1을 추가해주고,  좌표를 넣어준다.

 

 

O인 경우에는 방문 처리를 하며, 좌표를 넣어준다.

 

 

 

 

 

 

 

이러한 DFS 문제들은 공통점이 있다. 

 

 

https://mail-study.tistory.com/40

[백준] 14940번 : 쉬운 최단거리 (python 파이썬)

 

위 문제와 유사하게 DFS로 그래프를 확인하는 문제들은 공통적인 부분이 존재한다.

 

 

 

1. 어느 점을 기준으로 좌표를 이동한다.

 

2. 이동하면 일련의 로직을 수행한 후 다음 좌표를 덱에 넣어준다. 이때 방문 정보 등 , 후처리에 필요한 정보도 같이 넣어준다.

 

3. 방문한 좌표에 방문 처리를 해준다.

 

 

이 세가지의 커다란 덩어리가 있다고 생각한다.

 

 

 

여기에서 문제가 어떤 문제냐에 따라 각각의 덩어리에서 변형이 있다고 생각한다.

 

 

---

 

1번의 경우

 

1. 어느 점을 기준으로 좌표를 이동한다.

 

예를 들어 좌표를 이동하는 경우, 4가지 방향으로 갈지, 8가지 방향으로 갈지, 3차원인 경우인지.. 등으로 

 

방향과 칸 개수가 달라질 것이다. 

 

 

위의 정답 코드에서 

direction = [[0,1], [1,0],[0,-1],[-1,0]]

부분이 방향을 알려주는 것이다. 각각 y 와 x 좌표로 증가 혹은 감소치와 방향 정보를 가지고 있다.

 

 

    d2 = d.popleft()

    a,b = d2[0], d2[1]

 

덱에서 현재 좌표를 빼오면, direction을 for문을 돌면서 

 

  for dir in direction:

        if 0 <= a+dir[0] < n and 0<= b+dir[1] < m:

 

다음 좌표의 리스트의 인덱스의 초과 여부를 확인할 수 있다.

 

 

 

물론 if 문을 여러 번 사용하면서 direction을 사용하지 않을 수도 있지만, 

위의 방법이 수정과 테스트에 유리하고, 깔끔하다는 장점이 있다.

 

 

 

 

 

 

---

2번의 경우

 

 

2. 이동하면 일련의 로직을 수행한 후 다음 좌표를 덱에 넣어준다. 이때 방문 정보 등 , 후처리에 필요한 정보도 같이 넣어준다.

 

 

2번까지 왔다는 경우는 현재 좌표를 기준으로 이동까지 성공했다는 것을 의미한다.

   elif l[a+dir[0]][b+dir[1]] == "P":

                ans = ans+1

 

이처럼 이동한 좌표의 값이 P인 경우는 특이점이다. 

즉, 문제의 경우를 만족하고, 정답을 수정해하는 순간인 것이다.

 

따라서 ans 값을 하나 올려주는 방법으로 정답을 수정했다.

   d.append([a+dir[0], b+dir[1]])

그 후  다음 좌표를 덱에 넣어줬다. 

 

이 좌표가 다음 while 순서에서 현재 좌표가 될 것이다.

 

문제를 만족하는 경우 좌표를 넣어줬으므로, 가능한 경우는 모두 수행 가능하다고 할 수 있다. 

 

+++

 

여기에서 문제의 경우에 따라 후처리가 달라진다.

 

어떤 경우에는 기능을 한번만 수행하고, continue나 break로 다음 좌표로 바로 넘어가는 경우도 있지만,

 

 

어떤 경우에는 현재 수행한 행동을 덱에 넣은 후 다시 되돌려야 할 때도 있다.

 

 

for 문을 도는 것이 이유라고 할 수 있다.

 

 

for 문을 돌면 리스트의 순서대로 돌게 될 것이다.

 

순서대로 돈다는 것은 순서가 결과 값에 영향을 줄 수도 있다는 것이다. 

 

 

모든 경우가 그렇지는 않지만, 그런 경우도 있을 것이다.

 

 

어떤 정답 조건은 순서에 의존하지 않고, 무작위적인 경우인 경우도 있기 때문이다.

 

 

이처럼 순서에 의존하고 싶지 않다면,

 

 

정답을 수정한 후, 좌표나, 다른 조건들을 초기화함으로서 

 

for문의 첫번째나, 마지막 순서나 같은 조건으로 문제를 바라보게 할 수 있다.

 

 

 

 

---

 

3번의 경우

 

3. 방문한 좌표에 방문 처리를 해준다.

 

                l[a+dir[0]][b+dir[1]] = "-1"

 

 

 

개인적으로 방문 처리가 많이 중요하고 어려운 부분이라고 생각한다.

 

DFS 문제는 항상 한번 방문한 곳은 다시 방문하지 않는다.

 

 

방문한 곳을 다시 고려하지 않는다는 것은 수행 시간에 매우 큰 이점이 된다.

 

 

위 문제의 경우는 그래프의 좌표값을 "O" 가 아닌 다른 값으로 넣어줌으로 방문처리를 했다.

 

 

하지만 그래프를 건들 수 없는 경우도 있다.

 

 

 

위의 경우는 정답이 한 가지 뿐이다. 

 

 

어느 루트로 가던 정답은 한 가지이다. 

따라서 그래프 자체를 -1로 바꾸면서 방문 처리하면서 P를 찾아나갔다.

 

 

이 경우는 추가적인 메모리를 사용하지 않기 때문에 여러 장점이 있다.

 

 

 

 

하지만 정답의 형식이 최단루트라면 어떨까?

만약 최단루트가 여러가지면 또 어떻게 해야 할까?

 

1 0 0

0 0 0

0 0 2

 

위에서 1에서 2까지 가는 최단 루트는 6가지이다.

 

만약 이 최단 루트에서 특정 조건을 만족하는 루트의 개수를 구하라는 문제가 있다면 어떻게 해야 할까?

 

 

만약 그래프 자체를 바꾸면 어떻게 될까?

 

 

1 -1 -1

0  0 -1

0  0  2

 

한번 루트를 지나버리면, 다른 루트를 찾는데 영향을 끼쳐버린다.

 

 

 

따라서 

 

-1 0 0

 0 0 0

 0 0 0

 

과 같이 시작점을 방문 처리한 방문 정보가 따로 존재해야 한다.

 

 

현재 좌표를 기준으로, 지금까지 온 방문 정보를 덱에 넣음으로 답을 구할 수 있다.

 

 

만약 루트가 100가지라면 100가지의 방문 정보를 만들면 되는 것이다.

 

그러면 문제에서 제공하는 그래프를 손상시키지 않고 답을 구할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

이처럼 DFS 문제를 풀 때는 다음과 같은 공통점이 있다.

 

 

 

1. 어느 점을 기준으로 좌표를 이동한다.

 

2. 이동하면 일련의 로직을 수행한 후 다음 좌표를 덱에 넣어준다. 이때 방문 정보 등 , 후 처리에 필요한 정보도 같이 넣어준다.

 

3. 방문한 좌표에 방문 처리를 해준다.

 

 

 

정리하자면, 

덱에 집어넣는 객체들은 가능한 경우를 의미한다. 각각의 경우는 모두 독립적인 경우 이다.

이처럼 현재 경우의 수에서 가능한 다음 경우를 모두 덱에 넣어줌으로서 

가능한 모든 경우를 모두 구할 수 있는 것이다.!!