03-3. DFS/BFS問題解決

📝に質問白駿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なので出力しません.
入力
1行目は都市の個数N,道路の個数M,距離情報K,出発都市の番号Xを与える.(2≦N≦30000,1≦M≦100000,1≦K≦30000,1≦X≦N)2行目からM行を経て、2つの自然数A,Bをスペース基準で区切る.これは、A番都市からB番都市へ移動する一方通行道路があることを意味する.(1≦A,B≦N)セグメント,AとBは異なる自然数である.
しゅつりょく
Xから到達可能な都市では最短距離Kの全ての都市の番号が1行ずつ昇順に出力される.
このとき到達可能な都市のうち,最短距離Kの都市が1つも存在しなければ−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をDeckの右端に挿入します.
deque.Popleft():dakeの左端部分を取得し、dakeから削除します.

ちょっとその過程が理解できなくてコードを書いて理解しました!整理してみましたが、私だけが認識できるのは罠です...
今は分かりましたが、問題を見て書くと思うと、確かに少し迷っています.

📝問題2。白準14502号(研究所)

-質問

人体致命ウイルスを研究する研究所がウイルスを漏らした.幸いにもウイルスはまだ拡散していないので、ウイルスの拡散を防ぐために、研究所に壁を建てたいと思っています.
研究所の大きさはN×Mの矩形として表すことができ、矩形は1である.×1サイズの正方形に分割します.研究所は1つのスペース、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です.
研究所地図が与えられたタイミングで得られる安全領域の大きさの最値を求めるプログラムを作成した.
入力
第1行は、地図の縦方向サイズNおよび横方向サイズMを与える.(3 ≤ N, M ≤ 8)
2行目から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について、明日、勉強します.

📝に質問白駿2583号(取得エリア)

-質問

https://www.acmicpc.net/problem/2583
ルーラーピッチ1のM×N(M,N≦100)サイズの四角紙があります.この四角紙にK個の矩形を目盛りで描画すると、これらK個の矩形の内部を除いて、残りの部分はいくつかの別々の領域に分割される.
例えば、M=5、N=7の四角紙に<図1>のように3つの矩形を描くと、残りの領域は<図2>のように3つの独立した領域に分割される.

「図2」に示すように、3つの領域の幅はそれぞれ1、7、13である.
M,N,K,K個の矩形の座標が与えられると,K個の矩形の内部を除いた残りの部分をいくつかの独立した領域に分割し,各分離領域の幅を求めることで出力プログラムを記述する.
入力
第1行MとN,Kは、スペースを隔てて順次与えられる.M,N,Kはいずれも100以下の自然数である.2行目からK行目まで、矩形左下角頂点のx、y座標値、右上角頂点のx、y座標値は、行ごとにスペースを隔てて順次与えられる.四角い紙の左下の頂点の座標は(0,0)、右上の頂点の座標は(N,M)です.入力したK個の長方形は、丸み紙全体を埋めません.
しゅつりょく
最初の行の区切り領域の数を出力します.2行目は各領域の幅を昇順に並べ、スペースを隔てて印刷します.
入力例1
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2
サンプル出力1
3
1 7 13

-私のコード💻

-答えコード💻

-比較分析📖

整理1番問題(?)時間がかかりすぎたので、3日は復習時間か後で補習するので、😂😂😂