[백준] 21736 헌내기는 친구가 필요해 (python 파이썬)

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

---

평범한 그래프 탐색 문제. 

---

아이디어

bfs 또는 dfs를 활용하여 문제를 해결하면 된다. 

 

1. 그래프 시작지역 'I'는 캠퍼스 정보를 받아올 때 미리 찾아둘 수 있다.

2. 빈공간 뿐아니라 사람이 있는 지역 'P'도 이동 가능하다. 

3. 정답을 출력할 때, 답이 0명이면 0이 아닌 "TT"를 출력해 주자.

---

전체 코드

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
campus = [] # 캠퍼스 정보를 담는 리스트
ix, iy = 0, 0 # 최초 시작 위치의 좌표 ix, iy
answer = 0 # 만날 수 있는 사람의 수, 출력값

N, M = map(int, input().split()) # 캠퍼스 크기 입력

for i in range(N):
    campus.append(list(input()))
    for j in range(M):
        if campus[i][j] == 'I': # 시작 위치 찾기
            ix, iy = i, j

visited = [[0] * M for _ in range(N)] # 방문 정보를 담는 리스트

deq = deque()
deq.append([ix, iy]) # 최초 시작 위치 insert

while deq: # 큐가 빌 때까지
    x, y = deq.popleft()
    for i in range(4):  # 상하좌우 탐색
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0: # 방문 안했으면 
            visited[nx][ny] = 1 # 방문 표시
            if campus[nx][ny] == 'O':  # 빈 공간 이면 
                deq.append([nx, ny])
            elif campus[nx][ny] == 'P':  # 사람 이면
                deq.append([nx, ny])
                answer += 1 # 만난 사람 수 증가

print('TT' if answer == 0 else answer) # 정답 출력

---

코드 설명

for i in range(N):
    campus.append(list(input()))
    for j in range(M):
        if campus[i][j] == 'I': # 시작 위치 찾기
            ix, iy = i, j

 

캠퍼스 정보를 입력받으면서 시작 위치를 미리 찾았다.

 

 

deq = deque()
deq.append([ix, iy]) # 최초 시작 위치 insert

while deq: # 큐가 빌 때까지
    x, y = deq.popleft()
    for i in range(4):  # 상하좌우 탐색
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0: # 방문 안했으면 
            visited[nx][ny] = 1 # 방문 표시
            if campus[nx][ny] == 'O':  # 빈 공간 이면 
                deq.append([nx, ny])
            elif campus[nx][ny] == 'P':  # 사람 이면
                deq.append([nx, ny])
                answer += 1 # 만난 사람 수 증가

최초 시작 위치를 기준으로 bfs탐색을 했다. 캠퍼스 크기와 문제 조건에 맞게 if문을 작성해 준다.