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

그래프, BFS/DFS 문제

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

 

💡 풀이코드 (성공 - DFS 1)

import sys 
sys.setrecursionlimit(10 ** 9)  
r, c = map(int, sys.stdin.readline().split())
graph = []
start = []
visited = [[False] * c for _ in range(r)]
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
cnt = 0

for i in range(r):
    l = list(sys.stdin.readline().strip())
    for j in range(c):
        if l[j] == "I":
            start.append((i, j))
            visited[i][j] = True # 1) 시작 지점 방문 처리
    graph.append(l)


def dfs(rr, cc):
    global r, c, graph, cnt
    
    # if visited[rr][cc] == True:
    #     if graph[rr][cc] == "P":
    #         return 1 
    #     return 0
    
    # visited[rr][cc] = True

    for i in range(4):
        ny = dy[i] + rr 
        nx = dx[i] + cc 

        if 0 <= ny < r and 0 <= nx < c:
            if visited[ny][nx] == False:
                visited[ny][nx] = True # 2) 방문 처리

                if graph[ny][nx] != "X":
                    dfs(ny, nx)
                    if graph[ny][nx] == "P":
                        cnt += 1
             
dfs(start[0][0], start[0][1])
print("TT" if cnt == 0 else cnt)

 

접근 방식

• DFS
  • visited 배열을 만들고 False로 초기화
    • 상하좌우 탐색을 위해 for문을 도는데 만약 아직 방문하지 않은 좌표라면 방문처리를 진행
    • 만약 다음 이동좌표가 "X"라면 벽이란 의미로 이동 불가 -> dfs 호출 X
    • dfs에서 리턴한 후 만약 해당 좌표가 "P"였다면 전역 변수 cnt 1 증가
  • return값 설정 X
    • "P"를 만난다고 끝이 아니다.
      (다른 예시로, 그래프의 마지막 지점에 도달했을 때 (경로의) 갯수 세는 것과 느낌이 다름 -> return 가능)
    • 즉, "P"를 만난다고 return를 해버리면 더이상 탐색을 하지 못하므로 올바르지 못한 결과를 초래한다. (주석 코드)

 

💡 풀이코드 (성공 - DFS 2)

import sys 
sys.setrecursionlimit(10 ** 9)  
r, c = map(int, sys.stdin.readline().split())
graph = []
start = []
visited = [[False] * c for _ in range(r)]
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
cnt = 0

for i in range(r):
    l = list(sys.stdin.readline().strip())
    for j in range(c):
        if l[j] == "I":
            start.append((i, j))
            visited[i][j] = True
    graph.append(l)


def dfs(rr, cc):
    global r, c, graph, cnt
    
    if graph[rr][cc] == "P":
        cnt += 1

    for i in range(4):
        ny = dy[i] + rr 
        nx = dx[i] + cc 

        if 0 <= ny < r and 0 <= nx < c:
            if visited[ny][nx] == False:
                visited[ny][nx] = True

                if graph[ny][nx] != "X":
                    dfs(ny, nx)
                    # if graph[ny][nx] == "P":
                    #     cnt += 1
                
dfs(start[0][0], start[0][1])
print("TT" if cnt == 0 else cnt)

 

• 상하좌우 탐색을 위해 for문을 돌기 전 해당 좌표가 "P"인지 확인 
  • "P"라면 cnt 증가 
• dfs에서 리턴한 후 만약 해당 좌표가 "P"였다면 cnt 증가하는 것 X

 

💡 풀이코드 (성공 - BFS)

import sys 
from collections import deque 
r, c = map(int, sys.stdin.readline().split())
graph = []
start = deque()
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
visited = [[False] * c for _ in range(r)]
way = 0


for i in range(r):
    l = list(sys.stdin.readline().strip())
    for j in range(c):
        if l[j] == "I":
            start.append((i, j))
            visited[i][j] = True # 1) 시작지점 방문 처리 
    graph.append(l)


def bfs(graph, start):
    global visited, dy, dx
    cnt = 0 # 3) cnt - 전역으로 관리 

    while start:
        rr, cc = start.popleft()

        # visited[rr][cc] = True # 1) 시작지점 방문 처리 

        for i in range(4):
            ny = dy[i] + rr 
            nx = dx[i] + cc 
            
            if 0 <= ny < r and 0 <= nx < c:
                if visited[ny][nx] == False:
                    visited[ny][nx] = True # 2) 방문 처리 

                    if graph[ny][nx] == "X":
                        continue
                    elif graph[ny][nx] == "O":
                        start.append((ny, nx))
                    elif graph[ny][nx] == "P":
                        start.append((ny, nx))
                        cnt += 1
    return cnt

people = bfs(graph, start)
print("TT" if people == 0 else people)

 

접근 방식

• BFS
  • visited 배열을 만들고 False로 초기화 -> 방문하지 않았다면 방문 후 queue에 다음번 이동지 좌표 삽입
  • 만약 다음 이동좌표가 "X"라면 벽이란 의미로 이동 불가 -> queue에 삽입 X
  • 만약 다음 이동좌표가 "O"라면 빈 공간 -> 더 탐색을 위해 queue에 삽입
  • 만약 다음 이동좌표가 "P"라면 사람 -> 전역 변수 cnt를 1 증가 후 더 탐색을 위해 queue에 삽입
  • 사람의 수를 count한 변수를 나타내는 cnt를 리턴 

 

• 시작지점 방문 처리를 # 1)라고 명시한 두 부분 중 어느 부분에서 하든 상관 없다.
• 상하좌우 탐색을 위해 for문을 도는데 만약 아직 방문하지 않은 좌표라면 방문처리를 진행하고 "X"/"O"/"P"에 따라 분기된 로직을 실행한다.
• 처음에는 queue에 (ny, nx, cnt)를 삽입해주었는데, queue에 (ny, nx)만 삽입해주는 것으로 변경하였다.
  • 경로에 따라 마주칠 수 있는 "P"를 기록하는 것이 아니기 때문이다.
  • 즉, 그래프 내에서 마주칠 수 있는 전체 "P"의 갯수를 기록하면 된다.
  • 따라서, cnt를 전역으로 관리하게 변경해주었다.