
문제 링크
https://www.acmicpc.net/problem/21736
21736번: 헌내기는 친구가 필요해
2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고
www.acmicpc.net
중요
1. N x M 사이즈의 크기에서 '상하좌우로 이동' 한다고 제시되었습니다.
N과 M은 각각 행(row)과 열(col)이 되며 2차원 배열로 4방탐색을 한다면 쉽게 접근할 수 있겠습니다.
* 이동 제약조건으로 벽(X문자)만 있고, 다른 제한은 없으므로 DFS와 BFS 모두 사용할 수 있겠습니다.
2. O는 빈 공간, X는 벽, I는 도연, P는 사람. 단, I는 한 번만 주어짐이 보장.
도연(I문자)이 있는 곳이 시작 좌표인데, 반드시 값이 하나만 있으므로 시작 좌표를 담는 변수가 있으면 좋겠습니다.
벽(X문자)은 이동이 불가하므로 벽이 아닌 경우에만 이동 가능하다는 조건문이 있으면 좋겠습니다.
* DFS, BFS 둘 다 이전에 움직인(방문한) 위치에 다시 갈 수 있게 됩니다.
이는 '무한반복' 문제를 발생시켜 시스템에 치명적이므로 각각의 좌표는 단 한 번만 갈 수 있도록 작성합니다.
DFS (깊이 우선 탐색 - Depth First Search)
더 이상 접근할 수 없을 때까지 한 방향(깊이)으로만 들어가는(해당 값이나 좌표로 이동하는) 방법입니다.
계속 접근할 수 있다면 새로운 값이나 위치로 이동하게 됩니다.
그 값에서 다시 새로운 접근이 가능하다면 멈추지 않고 다음으로 이동합니다.
가능한 접근에 대해서 우선 처리되는 방식이므로 '재귀'를 이해하셨다면 접근하기 쉬운 방법입니다.
재귀의 처리 방식과 같은 결과를 도출할 수 있는 자료구조로 '스택(Stack)'을 적용합니다.
'예제 입력1'을 토대로 DFS 예시를 그린 그림입니다.
예시의 4방 우선순위는 "상 -> 우 -> 하 -> 좌"로 가정했습니다.

DFS 방식으로 작성한 Python Code입니다.
'재귀' 방식을 적용한 Method이며 Solution의 일부입니다.
import sys #재귀 사용 제한을 늘리는 목적 #기본값의 경우 대부분의 문제를 해결할 수 없으므로 적절히 제한 값을 크게 둔다. sys.setrecursionlimit(10**6) N = 'input의 N값' M = 'input의 M값' people = 0 #만난 사람 수 #상하좌우 이동을 위한 delta 배열 dxy = [[-1,0], [1,0], [-1,0], [1,0]] #row:도연(I)이 위치한 행(row) 값 #col:도연(I)이 위치한 열(col) 값 def DFS(row, col): global people for dx, dy in dxy: nx = row+dx ny = col+dy if nx<0 or nx>=N or ny<0 or ny>=M or arr[nx][ny] not in ('O', 'P'): continue if arr[nx][ny] == 'P': people += 1 arr[nx][ny] = 'X' #이전에 방문한 위치를 다시 가지 않기 위함 DFS(nx,ny)
BFS (너비 우선 탐색 - Breadth First Search)
현재 값(위치)에서 이동할 수 있는 가장 가까운 값(위치)를 가장 우선해서 처리하는 방법입니다.
다음으로 이동할 수 있는 값(위치)이 새롭게 들어왔다고 해도,
이전에 이동할 수 있는 다른 값(위치)이 먼저 들어와서 대기하고 있다면 그 값을 우선으로 처리해야 하는 방식을 가집니다.
그래서 "먼저 들어온 값을 우선 처리"하는 자료구조인 "큐(Queue)"를 사용합니다.
'예제 입력1'을 토대로 DFS 예시를 그린 그림입니다.
예시의 4방 우선순위는 "상 -> 우 -> 하 -> 좌"로 가정했습니다.

현재 위치에서 가장 가까운 값(위치) 중 가능한 경우를 모두 큐에 담아 우선 처리됩니다.
따라서 도연(I) 위치를 시작으로 상우하좌의 4방을 먼저 처리하고,
처리하는 과정에서 새롭게 담긴 값(위치) 중 '상' 방향에서 찾은 초록색 방향을 다음으로 처리합니다.
BFS 방식으로 작성한 Python Code입니다.
Method 안에 "큐(Queue)"를 사용해서 작성했습니다.
from collections import deque #deque 자료구조 사용 N = 'input의 N값' M = 'input의 M값' dxy = [[0,1], [0,-1], [1,0], [-1,0]] def BFS(row, col): cnt = 0 q = deque() q.append([row,col]) #도연(I)의 위치를 Queue에 담아 시작 while q: rr, cc = q.popleft() #가장 먼저 들어온 값을 꺼내서 사용 for dx, dy in dxy: nx = rr + dx ny = cc + dy if 0<=nx<N and 0<=ny<M and arr[nx][ny] in ('O', 'P'): if arr[nx][ny] == 'P': cnt += 1 arr[nx][ny] = 'X' q.append([nx,ny]) #다음 이동할 위치 값을 Queue에 담음 return cnt people = BFS(N, M)
DFS, BFS 포함 전체 코드
import sys; input=sys.stdin.readline from collections import deque sys.setrecursionlimit(10**6) N,M=map(int, input().split()) arr=[['' for _ in range(M)] for _ in range(N)] sr=sc=0 for r in range(N): for c,v in enumerate(input().rstrip()): arr[r][c] = v if v == 'I': sr=r sc=c people = 0 dxy = [[0,1], [0,-1], [1,0], [-1,0]] def DFS(row, col): global people for dx, dy in dxy: nx = row+dx ny = col+dy if nx<0 or nx>=N or ny<0 or ny>=M or arr[nx][ny] not in ('O', 'P'): continue if arr[nx][ny] == 'P': people += 1 arr[nx][ny] = 'X' DFS(nx,ny) def BFS(row, col): cnt = 0 q = deque() q.append([row,col]) while q: rr, cc = q.popleft() for dx, dy in dxy: nx = rr + dx ny = cc + dy if 0<=nx<N and 0<=ny<M and arr[nx][ny] in ('O', 'P'): if arr[nx][ny] == 'P': cnt += 1 arr[nx][ny] = 'X' q.append([nx,ny]) return cnt #주석 해제해서 사용 #DFS(sr,sc) #people = BFS(sr,sc) print('TT' if people==0 else people)

- 끝 -
'작업 > Problem Solving' 카테고리의 다른 글
프로그래머스 PCCP 기출문제 (동영상 재생기) - Python3 (0) | 2024.12.24 |
---|---|
백준(BOJ) 13913 숨바꼭질4 (Python3) (0) | 2023.05.05 |
백준 1107(리모컨) 파이썬(python3) 해결 (0) | 2022.05.08 |
프로그래머스 코딩 테스트 (신규 아이디 추천) - Python3 (0) | 2021.08.16 |
프로그래머스 위클리 챌린지 (2주차) - Python3 (0) | 2021.08.14 |