[알고리즘] 백준 21736 파이썬 - 헌내기는 친구가 필요해

 

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

문제

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 

도연이가 다니는 대학의 캠퍼스는 N X M크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x, y)에 있다면 이동할 수 있는 곳은 (x+1,y), (x,y+1), (x-1, y), (x, y-1)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

 

문제풀이

import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
graph=[]
visited=[[0]*m for _ in range(n)]

for i in range(n):
    graph.append(list(input()))
def dfs(x,y):
    global ans
    dx=[1,-1,0,0]
    dy=[0,0,1,-1]
    #01
    if 0<=x<n and 0<=y<m and not visited[x][y]:
        visited[x][y]=1
        if graph[x][y]=="P":
            ans+=1
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            #02
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
                if graph[nx][ny]!="X":
                    dfs(nx,ny)
ans=0
for i in range(n):
    for j in range(m):
    	#03
        if graph[i][j]=="I":
            dfs(i,j)
#04
if ans==0:
    print("TT")
else:
    print(ans)

- #01 : dfs 즉 #03에서 "I"값을 만나 dfs가 실행되었을 때의 값이 조건을 만족한다면,

          visited 값은 방문하였음을 표시하기 위해 1로 값을 변경한다.

          이후 graph 값이 "P"와 같다면 ans에 1을 더해준다.

- #02 : 이동한 좌표값인 nx와 ny가 조건을 만족한다면,

           graph 값이 "X"가 아니라면 dfs 함수를 재귀한다.

- #03 : i j 값을 for문으로 바꿔가며 graph가 "I" 값일 때 dfs 함수를 시작한다.

- #04 : ans가 초기값이라면 "TT"를 출력, 그렇지 않다면 ans를 출력한다.