BOJ(BaekJoon) 21736 Python Solve

 

문제 링크

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

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

 

중요

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)

 

 

- 끝 -