03-3. DFS/BFS 문제풀이

ji-vvon·2021년 7월 14일
2

알고리즘(파이썬)

목록 보기
15/41

📝문제1. 백준 18352번(특정 거리의 도시 찾기)

- 문제

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

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

입력
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

출력
X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

예제 입력 1
4 4 2 1
1 2
1 3
2 3
2 4
예제 출력 1
4

예제 입력 2
4 3 2 1
1 2
1 3
1 4
예제 출력 2
-1

예제 입력 3
4 4 1 1
1 2
1 3
2 3
2 4
예제 출력 3
2
3

- 나의 코드💻

# 최단 경로 문제 -> bfs 문제
from collections import deque


def bfs(graph, start, distance):
    global k, count
    queue = deque([start])
    distance[start] += 1
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if distance[i] == 0:
                queue.append(i)
                distance[i] += 1

    for p in distance:
        if p == k:
            print(count)
            count += 1
        else:
            count += 1

    if k not in distance:
        print("-1")


# n = 도시의 개수, m = 도로의 개수, k = 거리 정보, x = 출발 도시의 번호
n, m, k, x = map(int, input().split())
graph = []
for i in range(m):
    graph.append(list(map(int, input().split())))

distance = [0] * m
count = 1

bfs(graph, x, distance)

->나는 책의 bfs 예제를 따라하면서 살짝,, 많이 엉터리로 풀었다!!

- 정답 코드💻

from collections import deque

# n = 도시의 개수, m = 도로의 개수, k = 거리 정보, x = 출발 도시의 번호
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]

# 모든 도로 정보 입력받기
for _ in range(n):
    a, b = map(int, input().split())
    graph[a].append(b)

# 모든 도시에 대한 최단 거리 초기화
distance = [-1] * (n+1)
distance[x] = 0  # 출발도시까지의 거리는 0으로 설정


# BFS 수행
q = deque([x])
while q:
    now = q.popleft()
    # 현재 도시에서 이동할 수 있는 모든 도시를 확인
    for next_node in graph[now]:
        # 아직 방문하지 않은 도시라면
        if distance[next_node] == -1:
            # 최단 거리 갱신
            distance[next_node] = distance[now] + 1
            q.append(next_node)

# 최단 거리가 k인 모든 도시의 번호를 오름차순 정렬
check = False
for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        check = True

# 만일 최단 거리가 k인 도시가 없다면, -1 출력
if check == False:
    print(-1)

- 비교 분석📖

이 문제에서 모든 도로의 거리는 1이다. 이는 다시 말해 모든 간선의 비용의 1이라는 의미인데, 그래프에서 모든 간선의 비용이 동일할 때는 너비 우선 탐색(bfs)을 이용하여 최단 거리를 찾을 수 있다.
먼저 특정한 도시 x를 시작점으로 bfs를 수행하여 모든 도시까지의 최단거리를 계산한 뒤에, 각 최단거리를 하나씩 확인하며 그 값이 k인 경우에 해당 도시의 번호를 출력하면 된다.

[deque 문법]
deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.

뭔가 그 과정이 이해가 좀 안가서 코드를 쓰면서 이해해봤다,,! 정리 한다고 해본건데 나만 알아볼 수 있게 되어버린건 함정..
이제 이해는 가는데 내가 문제를 보고 작성할 생각을 하니 조금 막막하긴 하다!

📝문제2. 백준 14502번(연구소)

- 문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

예제 입력 1
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
예제 출력 1
27

예제 입력 2
4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2
예제 출력 2
9

예제 입력 3
8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
예제 출력 3
3

- 나의 코드💻

- 정답 코드💻

#문제 풀이과정
'''
1. 벽을 선택한다.
2. 바이러스를 퍼트린다.
3. 바이러스가 퍼지지 않은 안전지역 면적을 구한다.
1~3번의 과정을 벽을 선택하는 모든 경우의 수에 대해서 반복하고, 
마지막에 안전지역의 max값 리턴
'''
 
# input 및 변수선언
 
import copy
import sys
 
input = sys.stdin.readline
 
N, M = map(int, input().strip().split())
NM = []
for i in range(N):
    L = list(map(int, input().strip().split()))
    NM.append(L)
 
dr = [-1,0,1,0] # 위아래 row 단위로 이동
dc = [0,1,0,-1] # 좌우 column 단위로 이동
max_value = 0 # clean 지역의 개수를 return 하기 위한 변수
virus_list = [] # 바이러스 리스트 만들기
for i in range(N):
    for j in range(M):
        if NM[i][j] == 2:
            virus_list.append([i,j])
 
# 벽 선택하기
def select_wall(start,count):
    global max_value
    if count == 3 : # 종료조건, 벽 3개 선택 완료
        sel_NM = copy.deepcopy(NM) # deepcopy로 벽이 선택된 배열 복사
        for num in range(len(virus_list)):
            r, c = virus_list[num]
            spread_virus(r, c, sel_NM)
        safe_counts = sum(i.count(0) for i in sel_NM) # clean 지역 count
        max_value = max(max_value,safe_counts)
        return True
    else :
        for i in range(start, N*M): # 2차원 배열에서 조합 구하기
            r = i // M
            c = i % M
            if NM[r][c] == 0 : # 안전영역인 경우 벽으로 선택가능
                NM[r][c] = 1 # 벽으로 변경
                select_wall(i,count+1) # 벽선택
                NM[r][c] = 0
 
 
def spread_virus(r,c,sel_NM):
    if sel_NM[r][c] == 2:
        # 상하좌우 4방향을 확인하고 범위를 벗어나거나, 벽을만날때까지 반복
        for dir in range(4):
            n_r = r+dr[dir]
            n_c = c+dc[dir]
            if n_r >= 0 and n_c >=0 and n_r < N and n_c < M : # 범위를 벗어나지 않을때
                if sel_NM[n_r][n_c] == 0 :
                    sel_NM[n_r][n_c] = 2
                    spread_virus(n_r,n_c,sel_NM)
 
# 메인
select_wall(0,0)
print(max_value)


출처: https://mentha2.tistory.com/24 [행궁동 데이터 엔지니어]

- 비교 분석📖

단순한 변수 입력밖에 구현하지 못했다..

코드 출처
https://mentha2.tistory.com/24

우와우,, 정리를 정말 잘 해놓으셨다.. 조합과 dfs/bfs를 사용해 풀어야 하는 문제이다. 나는 dx, dy 배열을 통해 방향을 이동하는 그런 문제를 잘 풀지 못하는 것 같다. import copy, import sys 에 대해서 내일,, 공부하겠다.

📝문제3. 백준 2583번(영역 구하기)

- 문제

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

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력
첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

예제 입력 1
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2
예제 출력 1
3
1 7 13

- 나의 코드💻

- 정답 코드💻

- 비교 분석📖

1번 문제를 정리(?) 하느라 시간을 너무 많이 써서,, 3번은 복습 시간이나 추후 보강 예정,,입니다 😂😂😂

profile
ji-vvon
이전 포스트

03-2. DFS/BFS 문제풀이

다음 포스트

03-4. DFS/BFS 문제풀이

2개의 댓글

comment-user-thumbnail
biyam
2021년 7월 15일

안녕하세요, 김덕우입니다. 앞의 문제를 정말 잘 정리해놓으셨네요! 첫 문제에 많은 시간을 투자하다가 마지막 문제를 못 풀게되는 거 너무 공감합니다.. 그만큼 끈기있게, 집중해서 푸신 게 보여서 정말 멋져요. 오늘도 화이팅입니다!!

답글 달기
comment-user-thumbnail
Jifrozen
2021년 7월 15일

안녕하세요 알고리줌입니다!
저도 한문제 열심히 푸니깐 다음 문제는 잘 안풀리더라고요!!
오늘 수고 많으셨습니다!

답글 달기