[백준|파이썬] 21736: 헌내기는 친구가 필요해(DFS/BFS 풀이) (실버2)

문제

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

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

 

 

🐍파이썬

BFS

import sys
from collections import deque

def bfs(x, y):
    global cnt
    queue = deque()
    queue.append((x, y))
    sch[x][y] = 'X'	#방문처리
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= n or ny >= m or nx < 0 or ny < 0:
                continue
            if sch[nx][ny] == 'X':	#벽인 경우 건너뛰기
                continue
            if sch[nx][ny] == 'P':	#P인 경우
                cnt += 1	#만난 사람 카운트
                sch[nx][ny] = 'X'	#방문처리
                queue.append((nx, ny))	#현재 좌표를 기준으로 다음 경로로 이동
            if sch[nx][ny] == 'O':	#O인 경우
                sch[nx][ny] = 'X'	#방문처리
                queue.append((nx, ny))
        
n, m = map(int, sys.stdin.readline().split())
sch = []
for _ in range(n):
    sch.append(list(sys.stdin.readline().rstrip()))

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

cnt = 0
for i in range(n):
    for j in range(m):
        if sch[i][j] == "I":	#도연이의 위치에서 
            bfs(i, j)	#bfs실행

if cnt == 0:	#만난 사람이 없다면
    print("TT")
else:
    print(cnt)

 

DFS

import sys
sys.setrecursionlimit(10**6)

def dfs(x, y):
    global cnt
    if x >= n or y >= m or x < 0 or y < 0:
        return
    if sch[x][y] == 'X':	#벽인 경우 return
        return
    if sch[x][y] == 'P':	#사람을 만났다면 카운트
        cnt += 1
    sch[x][y] = 'X'	#방문처리
    for i in range(4):	#상하좌우에 대해 dfs실행
        nx = x + dx[i]
        ny = y + dy[i]
        dfs(nx, ny)
        
n, m = map(int, sys.stdin.readline().split())
sch = []
for _ in range(n):
    sch.append(list(sys.stdin.readline().rstrip()))

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

cnt = 0
for i in range(n):
    for j in range(m):
        if sch[i][j] == "I":	#도연이의 현재 위치에서
            dfs(i, j)	#dfs실행

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