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

DFS 문제를 7개 정도 풀어보니까 이제 어느정도 감이 잡힌다...

첫 제출이 바로 맞혀버린게 너무 행복해서 적는 블로그

이 문제는 백준 16173 문제를 풀었던 방식으로 풀었다

이 문제를 풀기 전에 24479 알고리즘 수업 문제를 풀었는데 여기서 global 전역변수를 선언한 방식을 고대로 사용하여 문제를 풀었다

사람을 만났을때 출력값인 cnt를 증가시켜야하므로 P 일때는 cnt가 증가하도록 해주었고
현재 위치가 X(벽)이 아니고, 이미 방문한 곳이 아니면 방문처리를 해주고 상하좌우 탐색을 해주었다

def DFS(x, y):
    global cnt
    if x <= -1 or y >= m or x >= n or y <= -1: return False
    else:
        if graph[x][y] == 'P':
            cnt += 1
        if graph[x][y] != 'X' and graph[x][y] != '1':
            graph[x][y] = '1' # 방문 처리
            DFS(x - 1, y)
            DFS(x + 1, y)
            DFS(x, y + 1)
            DFS(x, y - 1)

그리고 I의 위치가 DFS의 시작지점이므로 start 배열에다가 I의 위치를 저장해서 DFS를 시작해주었다

start = [[i,j] for i in range(n) for j in range(m) if graph[i][j]=="I"]
DFS(start[0][0], start[0][1])

전체 코드

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

n, m = map(int, input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(str, input())))

def DFS(x, y):
    global cnt
    if x <= -1 or y >= m or x >= n or y <= -1: return False
    else:
        if graph[x][y] == 'P':
            cnt += 1
        if graph[x][y] != 'X' and graph[x][y] != '1':
            graph[x][y] = '1' # 방문 처리
            DFS(x - 1, y)
            DFS(x + 1, y)
            DFS(x, y + 1)
            DFS(x, y - 1)
        
cnt = 0
start = [[i,j] for i in range(n) for j in range(m) if graph[i][j]=="I"]
DFS(start[0][0], start[0][1])

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

이 문제를 한번에 맞고 나니까 DFS 문제 자신감이 생겼다
불과 2년전만해도 DFS.. 그게 머야.. 어려워.. 상태였는데
뿌듯하다!!!!!!!