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

규갓 God Gyu·2024년 8월 3일

목록 보기

42/96

문제

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다.

도연이가 다니는 대학의 캠퍼스는
$N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가
( $x$ , $y$ )에 있다면 이동할 수 있는 곳은 ( $x+1$ , $y$ ), ( $x$ , $y+1$ ), ( $x-1$ , $y$ ), ( $x$ , $y-1$ )이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

입력

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수
$N$ (1 <= N <= 600), M (1 <= M <= 600)이 주어진다.

둘째 줄부터
$N$ 개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

예제 입력 1

3 5
OOOPO
OIOOX
OOOXP

예제 출력 1

예제 입력 2

3 3
IOX
OXP
XPP

예제 출력 2

TT

일단 문제 해석부터 매우 어려웠었는데, 코드로 정리해봄

최종 코드(가는 과정도 있음)

# 대학교 크기 N* M
# 상하좌우 이동(캠퍼스 밖 불가)
# N(1~600) M(1~600)
# o - 빈공간 x-벽 I-도연 P 사람
# 돌아가며 I를 찾으면 거기가 기준점
# 거기서 앞뒤좌우 더해가며 X로 막히면 로직 종료
# 안막히다 P만나면 count +1
# =========================================
# import sys

# input = sys.stdin.read
# data = input().split()

# # 위치 찾기 위한 범위
# N, M = int(data[0]), int(data[1])
# # 캠퍼스 정보
# campus_info = list(map(str, data[2:]))

# # 도연이 시작 위치
# doyeon = (0, 0)

# # N만큼 반복하면서
# for i in range(N):
#   # M만큼 반복하면서
#   for j in range(M):
#     # I찾으면 그게 도연이 위치
#     if campus_info[i][j] == 'I':
#       doyeon = (i, j)
#     # X찾을때까지 위치 옮길 예정
#     while campus_info[i][j] == 'X':
        
# # 여기까지가 내 한계
# ==========================================

from collections import deque

# 캠퍼스 크기
N, M = map(int, input().split())
# 리스트의 리스트로 담아 x,y좌표 접근하게 만들기(2차원 리스트)
campus = [list(input().strip()) for _ in range(N)]

# 도연이 위치 탐색
for i in range(N):
  for j in range(M):
    if campus[i][j] == 'I':
      start = (i, j)
      
# BFS(너비 우선 탐색) - 양쪽 삽입 삭제
queue = deque([start])
# 방문한 위치 저장 - 중복 방지 SET
visited = set([start])
# 사람 만난 횟수
people_count = 0

# 상하 좌우 이동 델타 설정(좌표 변화량)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# BFS 실행(queue가 있을땐 계속 실행)
while queue:
  # 최초 값 x ,y에 담아주기
  x, y = queue.popleft()
  
  # 4방향 탐색 루프
  for i in range(4):
    # 현재 위치 x , y에서 상하좌우 이동한 새로운 위치 계산
    nx, ny = x + dx[i], y+ dy[i]
    
    # nx, ny 캠퍼스 범위 내 설정, 벽 아니여야하고(X), visited에 담긴 값이 아닐때만!!
    if 0 <= nx < N and 0 <= ny < M and campus[nx][ny] != 'X' and (nx, ny) not in visited:
      # 방문한 곳에 저장
      visited.add((nx, ny))
      # 큐에 저장(현재값 갱신)
      queue.append((nx, ny))
      
      # 사람 만나면
      if campus[nx][ny] == 'P':
        people_count += 1
        
if people_count > 0:
  print(people_count)
else:
  print("TT")

# 대학교 크기 N* M
# 상하좌우 이동(캠퍼스 밖 불가)
# N(1~600) M(1~600)
# o - 빈공간 x-벽 I-도연 P 사람
# 돌아가며 I를 찾으면 거기가 기준점
# 거기서 앞뒤좌우 더해가며 X로 막히면 로직 종료
# 안막히다 P만나면 count +1

NxM의 크기만큼 공간이 채워져있음
최초 도연이의 위치 값을 찾아야함
상하좌우 움직여주면서 X안만나고 P를 찾으면 count +1

이 정도가 어떤 알고리즘 기법 없이 구할 수 있는 내 수준

# import sys

# input = sys.stdin.read
# data = input().split()

# # 위치 찾기 위한 범위
# N, M = int(data[0]), int(data[1])
# # 캠퍼스 정보
# campus_info = list(map(str, data[2:]))

# # 도연이 시작 위치
# doyeon = (0, 0)

# # N만큼 반복하면서
# for i in range(N):
#   # M만큼 반복하면서
#   for j in range(M):
#     # I찾으면 그게 도연이 위치
#     if campus_info[i][j] == 'I':
#       doyeon = (i, j)
#     # X찾을때까지 위치 옮길 예정
#     while campus_info[i][j] == 'X':
        
# # 여기까지가 내 한계

일단 sys의 read를 활용하여 모든 입력 값 data에 넣기
N, M 숫자로 변환하여 map을 이용해서 뽑아내기
campus_info변수에 리스트한 data str형식으로 넣기
ex) ['000x0','00000'] 이런식으로 문자열이 통째로 들어가게됨
도연이의 x,y좌표를 떠올리며 움직여야한다 판단해 () 튜플을 사용할 생각을 함
N,M만큼 x,y좌표 길이만큼 반복시키면서 I를 찾으면 그게 도연이의 시작 위치
그 이후로 막 앞뒤옆 돌아다니면서 P를 만나야하는데 이정도 수준까지가 내가 bfs? 이런거 모르고 찾을 수 있는 값

from collections import deque

# 캠퍼스 크기
N, M = map(int, input().split())
# 리스트의 리스트로 담아 x,y좌표 접근하게 만들기(2차원 리스트)
campus = [list(input().strip()) for _ in range(N)]

# 도연이 위치 탐색
for i in range(N):
  for j in range(M):
    if campus[i][j] == 'I':
      start = (i, j)
      
# BFS(너비 우선 탐색) - 양쪽 삽입 삭제
queue = deque([start])
# 방문한 위치 저장 - 중복 방지 SET
visited = set([start])
# 사람 만난 횟수
people_count = 0

# 상하 좌우 이동 델타 설정(좌표 변화량)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# BFS 실행(queue가 있을땐 계속 실행)
while queue:
  # 최초 값 x ,y에 담아주기
  x, y = queue.popleft()
  
  # 4방향 탐색 루프
  for i in range(4):
    # 현재 위치 x , y에서 상하좌우 이동한 새로운 위치 계산
    nx, ny = x + dx[i], y+ dy[i]
    
    # nx, ny 캠퍼스 범위 내 설정, 벽 아니여야하고(X), visited에 담긴 값이 아닐때만!!
    if 0 <= nx < N and 0 <= ny < M and campus[nx][ny] != 'X' and (nx, ny) not in visited:
      # 방문한 곳에 저장
      visited.add((nx, ny))
      # 큐에 저장(현재값 갱신)
      queue.append((nx, ny))
      
      # 사람 만나면
      if campus[nx][ny] == 'P':
        people_count += 1
        
if people_count > 0:
  print(people_count)
else:
  print("TT")