[21736] 헌내기는 친구가 필요해

bfs, dfs, 네방향 탐색 모두 c++로만 해보고 파이썬으론 처음 해봤다

기억도 가물가물해서 1260을 먼저 풀고 왔다

근데 네방향은 또 새로운 느낌 ㅎㅎ;

 

dfs 로 풀었는데 생각해보니까 시간초과가 날 수 밖에 없는..

경로를 구하는 문제가 아니라면 bfs로 무조건 생각해야지

 

c++에선 queue 쓰는게 쉬웠는데 여긴 좀 헷갈린다

import collections from deque

# 삽입 시 []로 묶어줘야 한다
q = deque([data])

# 앞에 데이터를 뽑을 시
q.popleft()

 

문제 풀 때 헷갈렸던 점

1. 입력 받을 때 strip() 처리

2. 방문 처리 : 맵 안쪽인지 확인하고 visited로 방문했는지 확인 

   만약 x가 아니라면(o와 p는 방문 가능하다) 방문처리하기

   q에 위치 저장하기

   p라면 개수 세기

 

import sys

from collections import deque

input = sys.stdin.readline

n,m = map(int, input().strip().split())

campus = []

for i in range(n):

    li = input().strip()

    campus.append(li)

    if 'I' in li:

        x = i

        y = li.find('I')

def bfs(x,y):

    q = deque([(x,y)])

    visited = [[False] * m for _ in range(n)]

    visited[x][y] = True

   

    cnt = 0

   

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

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

   

    while q:

        x, y = q.popleft()

        for i in range(4):

            nx = x + dx[i]

            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:

                if campus[nx][ny] != 'X':

                    visited[nx][ny] = True

                    q.append((nx,ny))

                    if campus[nx][ny] == 'P':

                        cnt += 1

    return cnt

   

answer = bfs(x,y)

if answer > 0:

    print(answer)

else:

    print('TT')