백준 BFS/DFS 문제입니다.

문제

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

[나의 풀이]

# N,M 크기 입력 받기
N , M = map(int,input().split())

# 캠퍼스
campus = []

# 도연좌표
doyeon = []


for i in range(N):
    tmp = list(input())
    campus.append([])
    for j in range(M):
        if tmp[j] == "I":
            doyeon.append(i)
            doyeon.append(j)
        campus[i].append(tmp[j])

# dfs 구현
stack = [doyeon]

# 초기 좌표 방문
campus[doyeon[0]][doyeon[1]] = 'X'

# 상우하좌
dx = [-1,0,1,0]
dy = [0,1,0,-1]
# 만난 친구 수
cnt = 0

while stack:

    v = stack.pop()

    if campus[v[0]][v[1]] == 'P':
        cnt += 1

    campus[v[0]][v[1]] = 'X'

    for i in range(4):
        
        newX = v[0] + dx[i]
        newY = v[1] + dy[i]

        if newX >=0 and newX < N and newY >= 0 and newY < M:
            if campus[newX][newY] != 'X':
                stack.append([newX,newY])

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

그래프 탐색 문제입니다. 이번에는 DFS로 구현하였으며 이전 다른풀이에서 배운대로 visited 리스트를 따로 생성하지 않고 지나온 좌표를 초기화하며 이후 탐색할 때 방문하지 않는 방식으로 구현하였습니다.🐤🐤🐤

[다른 사람의 풀이]

from collections import deque
from sys import stdin
input = stdin.readline

def BFS(sx, sy) :
    visited = [[False] * M for _ in range(N)]
    visited[sx][sy] = True
    queue = deque([(sx, sy)])
    meet = 0
    while queue :
        x, y = queue.popleft()
        for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] :
            if 0 <= nx < N and 0 <= ny < M and board[nx][ny] != 'X' and not visited[nx][ny] :
                visited[nx][ny] = True
                queue.append((nx, ny))
                if board[nx][ny] == 'P' :
                    meet += 1
    return ['TT', meet] [meet > 0]

N, M = map(int, input().split())
board = [[] for _ in range(N)]
sx, sy = -1, -1
for i in range(N) :
    board[i] = [*input()]
    for j in range(M) :
        if board[i][j] == 'I' :
            sx, sy = i, j
print(BFS(sx, sy))

BFS로 해결한 방식 또한 볼 수 있었는데 이때 저의 풀이처럼 자신이 이미 지나온 좌표를 'X' 즉, 벽으로 간주하여 vistied 리스트를 체크하지 않아도 구현이 가능합니다.🐦🐦🐦

조금 특이한 점은 bfs() 함수에서 반환할 때

return ['TT',meet] [meet > 0]

으로 구현한 부분이 처음 보는 형태의 문법이었습니다.

감사합니다.