[BOJ][Python]21736 풀이

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

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

from collections import deque
import sys
ssr = sys.stdin.readline

def check_pos():
    p_cnt = 0
    for i in range(n):
        for j in range(m):
            if campus[i][j] == 'I':
                q.append((i, j))
                campus[i][j] = 'X'
            elif campus[i][j] == 'P':
                p_cnt += 1
    return p_cnt
                
def bfs():
    ans = 0
    while q:
        r, c = q.popleft()
        for dr, dc in dir:
            if 0 <= r+dr < n and 0 <= c+dc < m and campus[r+dr][c+dc] != 'X':
                if campus[r+dr][c+dc] == 'P':
                    ans += 1
                q.append((r+dr, c+dc))
                campus[r+dr][c+dc] = 'X'
    return ans                       
                
n, m = map(int, ssr().split())
campus = [list(ssr().rstrip()) for _ in range(n)]
dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque([])
p_cnt = check_pos()
ans = bfs()
print(ans if ans != 0 else 'TT')

간단한 그래프 탐색 문제입니다. 뭐랄까 예전에는 dfs는 할 줄 알아도 bfs를 할 줄 몰라서 쩔쩔맸던 기억이 있는데, 이제는 dfs보다 bfs가 훨씬 편하고 자주 쓰는 걸 보면 감회가 새롭네요.

 

크게 어려운 문제는 아니니까요. 어떻게 하면 시작 포지션을 정할지, 몇명의 사람이 존재하는지, 어떻게 하면 만나는 사람을 체크할 것인지 등을 고민하면 쉽게 풀 수 있는 문제라고 생각합니다. 다만 그래프 탐색 문제가 아직 익숙하지 않으신 분들은 좀 힘드실 수도 있겠다는 생각이 드네요.

 

저는 그래프 탐색 문제를 공부할 때 처음에 상당히 헤맸습니다. 딱히 배운 적도 없고 이차원배열 자체도 그다지 많이 사용해보지 않았다보니 훨씬 힘들어했던 것 같아요. 다익스트라 알고리즘을 공부하던 때처럼 이해가 안되어서 유튜브도 보고 글도 찾아보고 문제도 풀고 하면서 고군분투 했었는데요. 저는 개인적으로 solved.ac의 클래스 3 문제를 거의 다 풀 때 쯤에 기본적인 그래프 탐색에 많이 익숙해졌습니다. 여전히 어려운 탐색 문제들은 잘 못풀지만요(이미 갔던 곳을 중복해서 갈 수 있는 문제라든가). 오래걸려도 좋으니까 클래스 3 문제를 풀고 모르면 풀이를 보고 다 푼 다음에 다른 사람들의 풀이를 찾아보고 하다보면 아마 어느 순간 익숙해져있는 자신을 보게될 것이라고 생각합니다.