[Baekjoon] 백준 21736 '헌내기는 친구가 필요해' 문제풀이 Python, 파이썬, 알고리즘 정리

 

📝 21736 문제 

 

입력 

 

출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

 

🧐 풀이

위의 문제는 그래프 문제이다.

캠퍼스의 크기 NxM을 입력 받고, 캠퍼스 정보가 주어진다. 먼저 정보를 입력 받으면서 도연이가 있는 곳을 찾아야 한다. 

'I' 가 나온 곳을 찾고, 그 위치를 start로 한다. 그리고 벽이 아니고, 방문하지 않으며 'P'인 경우에는 cnt를 증가시키고, 'X'인 경우에는 가지 못하니 다시 탐색을 해야한다.  

cnt가 0이 아니라면 'TT'를 출력한다. 

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
campus = []


#입력 받으면서 도연이가 있는 곳을 찾기 
for i in range(N) :
    r = list(input().rstrip())
    for j in range(M) :
        if r[j] == 'I' :
            start = [i, j]
    campus.append(r)
    
    
#상하좌우 탐색하기 위함            
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False] * M for _ in range(N)]
cnt = 0


def dfs(x, y) :
    global cnt 
    
    if 0<=x<N and 0<=y<M and not visited[x][y]:
        visited[x][y] = True
        if campus[x][y] == 'P' :	#사람이 있는 곳이라면	
            cnt += 1	#cnt 증가
        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]  
            if 0<=nx<N and 0<=ny<M :
                if campus[nx][ny] != 'X' and not visited[nx][ny] :
                    dfs(nx, ny)
dfs(start[0], start[1])
            
      

if cnt > 0 : 
    print(cnt)
else :
    print('TT')