[백준] 21736 - 헌내기는 친구가 필요해

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

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

문제 한줄 이해

-그래프의 특정 위치에서 이동하면서 친구 만나기

 

생각난 풀이

1번째 방법: 전형적인 dfs, bfs 문제라 생각이 들어 dfs를 활용해 문제를 풀었다.

import sys
n, m = map(int,sys.stdin.readline().split())
graph = []

for i in range(n):
    graph.append(list(map(str, sys.stdin.readline().rstrip())))

#먼저 도연이 위치 찾기
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'I':
            nowx = i
            nowy = j
            break
        
def dfs(x,y):
    global cnt
    # 그래프 범위를 벗어나면 종료
    if x<0 or y<0 or x>n-1 or y>m-1:
        return
    
    # I,O,P면 탐색 가능
    if graph[x][y] == 'I' or graph[x][y] == 'O' or graph[x][y] == 'P':
        if graph[x][y] == 'P':
            cnt +=1
        graph[x][y] = -1
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x,y-1)
        
cnt = 0        
dfs(nowx,nowy)
if cnt == 0:
    cnt = 'TT'
print(cnt)