[Python] 21736. 헌내기는 친구가 필요해(실2) - BFS 기초 탐색 문제

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

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

---

2. 핵심 아이디어

사실 아이디어라고 할 것이 없다.

BFS 기초 탐색문제인 만큼 정석적으로 꺼내서 판단하고 넣어주면 되는 문제였다.

기초 탐색 문제를 많이 풀어보았다면 쉽게 풀 수 있는 문제

---

3. 코드

from collections import deque

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

data=[]
start=0

#사람 1 벽 -1 빈공간 0
for j in range(n):
  listk=list(input())
  temp=[]
  for idx, i in enumerate(listk):
    if i=="O":
      temp.append(0)
    elif i=="X":
      temp.append(-1)
    elif i=="I":
      start=(j, idx)
      temp.append(0)
    elif i=="P":
      temp.append(1)
  data.append(temp)


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

def bfs(a,b):
  q=deque([(a,b)])
  data[a][b]=0
  cnt=0

  while(q):
    x, y= q.popleft()
    for i in range(4):
      nx= x+dx[i]
      ny= y+dy[i]

      if nx<0 or ny<0 or nx>=n or ny>=m:
        continue
      
      if data[nx][ny]==0:
        data[nx][ny]=-1
        q.append((nx, ny))
      elif data[nx][ny]==1:
        data[nx][ny]=-1
        cnt+=1
        q.append((nx, ny))
  return cnt

result= bfs(start[0], start[1])

if result==0:
  print("TT")
else:
  print(result)

---

4.배운 점

지금 다시보니 굳이 숫자로 변경하지 않더라도 문제를 풀 수 있음을 알았다.

숫자판단이 비교가 쉽다보니 습관적으로 문자-> 숫자화를 시키려 한 것 같았다.

 

문자 자체를 다루는 방법도 생각해보자.

문자도 숫자다.