[Python] 백준 21736번 문제풀이

문제 링크

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

아이디어

1. 처음에 도연이의 위치를 이중반복문을 통해 찾아내서 x,y에 저장해두고

2. 도연이의 위치로 dfs를 시작해서

3. 만날 수 있는 사람의 수를 res에 저장하고

4. res가 0이라면 "TT"를 출력하고 아니라면 res 그대로 출력

 

소스코드

"""
1. 아이디어
  - 도연이의 위치를 찾는다
  - 도연이 위치에서부터 dfs 시작한다.
  - 방문하면서 P를 찾으면 결과에 1을 더하고
  - 마지막에 출력할 때 0이면 TT 출력하고 아니면 그 숫자 출력

2. 시간복잡도
  - 위치 찾기 = h(600) * w(600) = 36000
  - O(V + E) =  O(V + 4V) = O(5V) = 36000*5 = 180000
  
3. 자료구조
  - graph : str[][]
  - visited : bool[][]
  - res, x, y : int
"""

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

h, w = map(int, input().split())

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

graph = []
for i in range(h):
    graph.append(list(input().strip()))

visited = [[False] * w for _ in range(h)]

x = y = res = 0

for i in range(h):
    for j in range(w):
        if graph[i][j] == 'I':
            x = j
            y = i
            break

def dfs(y, x):
    global res
    if graph[y][x] == 'P':
        res += 1
    visited[y][x] = True

    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]
        if (0<=ny<h) and (0<=nx<w):
            if not visited[ny][nx] and graph[ny][nx] != 'X':
                dfs(ny, nx)

dfs(y, x)

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