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

✏️ 문제  

 

문제 파악

입력으로 주어진 값을 잘 구분해야 한다.

• X → 벽이므로 아예 방문을 자체를 안해도 됨
• I → 도연이의 위치로, 즉 탐색의 초기 위치 값
• P → 사람이 있는 위치로 이 위치에 해당될 때만 카운트 

 

또한 이 문제의 경우 가로, 세로로 이동해서 방문할 수 있으니 방향 배열을 다음과 같이 구성했다.

d = [(-1, 0), (1, 0), (0, -1), (0, 1)]

 

 

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

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

n, m = map(int, input().split())
graph = [[0] * m for _ in range(n)]
visited = [[0] * m for _ in range(n)]
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
start_x, start_y = 0, 0
people = 0

for i in range(n):
  s = input()
  for j in range(m):
    if s[j] == 'X':
      visited[i][j] = -1
    elif s[j] == 'I':
      start_x, start_y = i, j
    elif s[j] == 'P':
      graph[i][j] = 2

def bfs(x, y):
  cnt = 0
  q = deque([(x, y)])
  visited[x][y] = 1
  
  while q:
    x, y = q.popleft()

    for i in range(4):
      dx = x + d[i][0]
      dy = y + d[i][1]

      if 0 <= dx < n and 0 <= dy < m and visited[dx][dy] == 0: 
        if graph[dx][dy] == 2:
          cnt += 1
        visited[dx][dy] = 1
        q.append([dx, dy])
  
  return cnt

people = bfs(start_x, start_y)
print('TT' if people == 0 else people)

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS