알고리즘/백준 문제풀이

[boj] 백준 21736 헌내기는 친구가 필요해 python 풀이

감자156 2023. 8. 8. 00:33
반응형

문제

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

 

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

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

www.acmicpc.net

 

문제 풀이

bfs

 

코드

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

N,M = map(int,input().split())
Map = [[] for _ in range(N)]

for i in range(N):
    string = input().strip()
    if 'I' in string:
        x_idx, y_idx = i,string.index('I')
    Map[i] = list(str(string))

def bfs():
    move = {(-1,0),(0,1),(1,0),(0,-1)}
    
    q = deque()
    q.append((x_idx,y_idx))
    Map[x_idx][y_idx] = 1
    res = 0

    while q:
        x, y = q.popleft()
        for tx,ty in move:
            nx = x + tx
            ny = y + ty

            if 0<=nx<N and 0<=ny<M \
                and Map[nx][ny] != 'X' and Map[nx][ny] != 1: 
                q.append((nx,ny)) 
                if Map[nx][ny] == 'P':
                    res += 1  
                Map[nx][ny] = 1 
    
    if res == 0:
        print('TT')
    else: print(res)

bfs()
반응형