[백준21736] / 헌내기는 친구가 필요해 - 그래프(BFS)

 

 

 

푼 날짜 : 2024.07.25

푼 문제 : [21736] / 헌내기는 친구가 필요해

사용한 언어 : python

 

 

푼 방법 :

너비 우선 탐색으로 접근

어휴 이제는 척하면 척! 쉽다 쉬워(정말?)

 

'X' 인 경우는 벽이기 때문에 이동을 막고, 'O' 와 'P' 의 경우에는 이동을 허용한다.

이때 'P'인 경우 정답 += 1 해준다.

( ans 가 0일 경우 친구를 못만나서 슬프니까 'TT' 출력하기 ! )

 

 

코드 :

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
graph_ = []

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

def BFS(graph_, visited, v):
    queue = deque([(v)])
    visited[v[0]][v[1]] = 1

    ans = 0
    while queue:
        now = queue.popleft()
        for i in range(4):
            ny, nx = now[0]+dy[i], now[1]+dx[i]
            if 0<=ny<N and 0<=nx<M:
                if not visited[ny][nx] and graph_[ny][nx] != 'X':
                    queue.append((ny, nx))
                    visited[ny][nx] = 1   
                    if graph_[ny][nx] == 'P':
                        ans += 1  

    print(ans if ans else 'TT')

x, y = 0, 0
for i in range(N):
    row = list(sys.stdin.readline().strip())
    for j in range(len(row)):
        if row[j] == "I":
            y = i
            x = j
    graph_.append(row)

visited = [[0 for _ in range(M)] for _ in range(N)]
BFS(graph_, visited, (y, x))

 

 

그래프 두려워 했던 과거의 나는 이제 없다!!! *.☆⸜(⑉˙ᗜ˙⑉)⸝♡.*

 

 

 

+ 백준 골드까지 2점 남아서 신나!!!