헌내기는 친구가 필요해 (백준)

from queue import Queue

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

count = 0
area = []
initial_state = 0
for i in range(n):
    row = list(input())
    if 'I' in row:  # 현재 위치 기록
        initial_state = (i, row.index('I'))
    area.append(row)

queue = Queue()
queue.put(initial_state)
visited = set()
visited.add(initial_state)

while not queue.empty():
    x, y = queue.get()

    if area[x][y] == 'P':
        count += 1

    for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0):
        nx, ny = dx + x, dy + y#좌표

        if 0<=nx<n and 0<=ny<m and area[nx][ny] != 'X' and (nx,ny) not in visited:
            queue.put((nx, ny))
            visited.add((nx, ny))

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

 

탐색을 해야 하는 문제라 BFS를 이용해서 문제를 해결 하였다.

1차원 리스트로 접근해서 문제를 풀다가 접근방식이 직관적이지 못해 2차원 리스트로 변환해서 풀었다.

추가로 탐색한 노드가 X라면 큐에 넣지 않으면 되므로 X일경우를 고려하여 BFS에 조건을 추가하였다.

 

* BFS

넓이 우선 탐색:

초기 노드를 임의로 정하여 탐색을 시작한후 인접한 노드를 큐에 집어 넣는다.

탐색이 끝난후 노드 중복 탐색 방지를 위해 검사후 방문한 노드 리스트에 집어 넣는다.

큐에 있는 노드를 꺼낸 다음 탐색후 똗같이 인접한 노드를 집어 넣는다.