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

문제

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

 

접근 방법

아이디어 내기

1. 도연이의 위치인 I에서 시작하기
   • 캠퍼스의 정보를 가져올 때, I위 위치도 가져올 수 있다!
2. 빈 공간인 O와 사람이 있는 P는 이동이 가능하다
3. 만난 사람이 0명이면 TT를 반환하고, 만난 사람이 있으면 몇명 만났는지 출력하기

1. 초기 설정

• 그래프 탐색을 위해 BFS이용할 것 -> 큐 사용하기
• dx, dy를 통해 상하좌우 이동하기
• ix, iy를 통해 시작위치인 도연이 위치 설정하기

from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
campus = []  # 캠퍼스 정보를 담을 리스트
ix, iy = 0, 0  # 시작 위치 초기화
meet = 0  # 만난 사람 수 초기화

 

2. 입력 및 초기화

• 캠퍼스의 정보 입력받아 'campus' 리스트에 저장하기. 각 행마다 문자를 리스트로 변환하여 저장하기
• I의 위치를 찾아서 'ix', 'iy'에 시작 위치를 저장하기

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':  # 'I'가 있는 위치를 시작 위치로 설정
            ix, iy = i, j

 

3. BFS를 위한 큐 및 방문 기록 초기화

• visited 리스트를 통해 각 위치의 방문 여부를 확인한다
• 'deq'는 BFS를 위한 큐로, 시작 위치를 큐에 넣는다

visited = [[0] * m for _ in range(n)]  # 방문 정보를 저장할 리스트
deq = deque()
deq.append([ix, iy])  # 시작 위치를 큐에 추가

 

4. BFS탐색

• 큐가 빌 때까지 반복하여 BFS를 수행한다
• 현재 위치에서 상하좌우로 이동할 수 있는 위치를 탐색한다
• 이동할 위치가 캠퍼스 범위 내에 있고 아직 방문하지 않은 경우:
  • 해당 위치를 방문으로 표시한다
  • 그 위치가 빈 공간('O')이라면 큐에 추가하여 계속 탐색한다
  • 그 위치에 사람이 있다면('P'), 큐에 추가하고 meet를 1 증가시킨다

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])  # 큐에 추가하여 계속 탐색
                meet += 1  # 만난 사람 수 증가

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

 

 

전체 코드

from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
campus = [] #캠퍼스 정보 담기
ix, iy = 0, 0 #시작 위치 초기화
meet = 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': #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])  # 큐에 추가하여 계속 탐색
                meet += 1  # 만난 사람 수 증가

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