【AtCoder版！蟻本】AOJ 1160 How Many Islands?【深さ優先探索】

AtCoder版！蟻本の深さ優先探索で類題としてあげられているAOJ 1160 How Many Islands?をPythonで解いていきます。

リンク

AOJ 1160

AOJ 1160 How Many Islands?

問題文

陸に対応する二つの正方形領域が，地図上で縦，横または斜め方向に隣接しているなら，一方から他方へ歩いて行くことができる． 陸に対応する二つの領域が同じ島に属するのは，一方から他方へ（一般には別の陸地を経由して）歩いて行ける時であり，またその時のみである． なお，この地図の海域は海で囲まれており，その外側へ歩いて出ることはできない．

与えられた地図を読み取り，この海域に島がいくつあるか数えるプログラムを作成して欲しい．

制約

・ w と h は地図の幅と高さを表す50以下の正の整数
・ci, j は，0 または 1 であり，空白文字1個で区切られる
・ci, j = 0 なら，地図上で左から i 番目，上か ら j 番目の正方形は海であり，ci, j = 1 なら陸である

解答例

import sys
sys.setrecursionlimit(10**7) #再帰回数の上限変更

# マスy,xに隣接する陸を海に置き換え
def dfs(y,x):
    # 現在地を0に置き換え
    field[y][x] = 0
    # 周囲8マスをループ
    for dx in range(-1,2):
        for dy in range(-1,2):
            # 移動後のマスをny,nxとする
            ny = y + dy
            nx = x + dx

            # ny,nxがfield内で陸かどうかを判別
            if 0 <= nx < w and 0 <= ny < h and field[ny][nx] == 1:
                dfs(ny,nx)
    return


while True:
    w, h = map(int,input().split())
    if w == 0 and h == 0:
        break
    field = []
    for _ in range(h):
        array = list(map(int,input().split()))
        field.append(array)
    
    # 島の数
    ans = 0

    for i in range(h):
        for j in range(w):
            if field[i][j] == 1:
                dfs(i,j)
                ans += 1

    print(ans)

解説

地図上の島の数をカウントする問題で、DFSを使って探索していきます。

これまでのDFSの問題とほとんど同じですが…
地図の各マスを全探索して島であればDFSします。
島のマスを海に置き換えて、周囲9マスに島があるか探します。
島があれば、またそのマスを海に置き換えて、という処理を繰り返して周囲に島がなくなれば島の数を1つ増やしていきました。
全探索が終わればすべて海に置き換わり、島の数がカウントできています。
最後に島の数を出力すればOKです。

このプログラムはデフォルトの再帰回数の上限を超えてしまいます。
上限を10^7に変更しないとエラーになりましたので注意してください。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

【AtCoder版！蟻本】ARC 037 B - バウムテスト【深さ優先探索】

AtCoder版！蟻本の深さ優先探索で類題としてあげられているARC037 BをPythonで解いていきます。
DFSを使ってグラフの連結成分に閉路があるか判別していきます。

リンク

atcoder.jp

AtCoder Regular Contest 037 B - バウムテスト

問題文

バウムテストとは、被験者に「木」の絵を描かせることで被験者の心理状態を読み取る心理検査である。この検査を受けた高橋君は、 N 個の頂点と M 本の辺からなる無向グラフを描いた。
このグラフの連結成分のうち木であるようなもの、すなわち閉路を持たないものの個数を求めよ。

制約

・ N (2 ≦ N ≦ 100)
・M (1 ≦ M ≦ N×(N−1)/2)
・ i+1 行目 (1 ≦ i ≦ M) には、辺 i が結ぶ 2 頂点の番号 ui, vi (1 ≦ ui ＜ vi ≦ N) がスペース区切りで与えられる。
・どの 2 頂点についても、それらを直接結ぶ辺は高々 1 本しか存在しない。

解答例

# 深さ優先探索
from collections import deque

n, m = map(int,input().split())

U = []
V = []
for i in range(m):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    U.append(u)
    V.append(v)

# 閉路を持たない木
ans = 0
# 探索済み頂点リスト
Visited = [0] * n

# 頂点iからdfs 探索済み頂点リストを更新していき 探索済み頂点をpopしたら閉路
def dfs(i):
    que = deque()
    que.append(i)       # 探索をはじめる頂点をpush
    flag = True         # 閉路判別フラグ Trueで閉路なし
    
    # queが空になるまで探索
    while len(que) != 0:
        k = que.pop()   # 探索する頂点kをpop
        if Visited[k] != 0:
            flag = False
        else:
            Visited[k] = 1    # 頂点kの探索済みリストを更新
            for j in range(m):
                # 未探索の頂点ならpush
                if U[j] == k and Visited[V[j]] == 0:
                    que.append(V[j])
                elif V[j] == k and Visited[U[j]] == 0:
                    que.append(U[j])
                
    #頂点iからの探索を終えたとき閉路があるかを返す
    return flag

# すべての頂点で未探索ならdfs
for l in range(n):
    if Visited[l] == 0:
        if dfs(l): # 探索して閉路がなければans+1
            ans += 1

print(ans)

解説

N個の頂点があり、2つの頂点をつなぐ辺がM本あるとき、辺でつながった連結成分のうち木である（閉路がない）ものの数を答える問題です。

0で初期化した探索済み頂点リストVisitedを作成し、DFSで探索していきます。
探索した頂点はVisitedの該当要素を+1してメモしていきました。

連結成分が木であるか閉路があるかの判断はVisitedを用います。
閉路があるときは探索済みの頂点がpopされますが、木である場合は探索済みの頂点がpopされることはないです。
これをflag管理して木である連結成分の数をカウントしていきました。

全頂点が探索済みとなればカウントしていた木の数を出力すればOKでした！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

【AtCoder版！蟻本】ARC 031 B - 埋め立て【深さ優先探索】

AtCoder版！蟻本の深さ優先探索で類題としてあげられているARC031 BをPythonで解いていきます。
再帰関数を使用して解いています。

リンク

atcoder.jp

AtCoder Regular Contest 031 B - 埋め立て

問題文

とある所に島国がありました。島国にはいくつかの島があります。このたび、この島国で埋め立て計画が立案されたのですが、どこを埋め立てるか決まっていません。できることなら埋め立てによって島を繋いで、1 つの島にしてしまいたいのですが、たくさん埋め立てるわけにもいきません。
10 マス × 10 マスのこの島国の地図が与えられるので、1 マスを埋め立てた時に 1 つの島にできるか判定してください。ただし、地図で陸地を表すマスが上下左右につながっている領域のことを島と呼びます。

制約

・各行は 10 文字からなり、o は陸地を、x は海を表す。
・少なくとも 1 マスは陸地があることが保証される。
・少なくとも 1 マスは海があることが保証される

解答例

import copy

Map = [] # 10*10マスの地図
for _ in range(10):
    Map.append(list(input()))

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# 現在地に隣接する陸地を海に置き換える
def dfs(x, y):
    # 今いるところをxに置き換える
    if New_map[x][y] == "o":
        New_map[x][y] = "x"
    for k in range(4): # x方向にdx y方向にdy 移動した場所を(nx, ny)とする
        nx = x + dx[k]
        ny = y + dy[k]
        # nxとnyがMap内で陸地か判別
        if 0 <= nx < 10 and 0 <= ny < 10 and New_map[nx][ny] == "o":
            dfs(nx,ny)
    return

for i in range(10):
    for j in range(10):
        if Map[i][j] == "x":
            New_map = copy.deepcopy(Map)
            dfs(i,j)
        else:
            continue
        
        flag = True
        for a in range(10):
            for b in range(10):
                if New_map[a][b] == "o":
                    flag = False
        if flag:
            print("YES")
            exit()
else:
    print("NO")

解説

10×10マスの島国の地図があり、海を1マスだけ陸に変えたときに1つの島になるか判定する問題です。

初期状態のマップのうち各マスを全探索し、海であればその地点をDFSに渡します。

DFSでは渡された地点から縦横4マスに陸地があれば海に置き換えていきます。
スタート地点から隣接した陸はすべて海になります。
この後に海に置き換えた地図に陸地がないか全探索します。
これで陸地がないことを確認できたらYESを出力し、ループが抜けてしまったらNOを出力すればOKです。

ループごとにdeepcopyを使ってNew_mapを初期化しないと引き継ぎたくないのに引き継がれてしまい苦労しました。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

【AtCoder版！蟻本】ATC 001 A 深さ優先探索【深さ優先探索】

AtCoder版！蟻本の深さ優先探索で類題としてあげられているATC001 AをPythonで解いていきます。
深さ優先探索（DFS）は初めて見たとき難しく感じましたが、何問か解くとイメージがわいてきました。
理解しないと使いこなせないと思いますので頑張って取り組んでいきます。

リンク

atcoder.jp

AtCoder Typical Contest 001 A - 深さ優先探索

問題文

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

制約

・H(1≦H≦500)
・W(1≦W≦500)
・ci,j(0≦i≦H−1,0≦j≦W−1)
・i 行目 j 文字目の文字 ci,j はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。
・s : その区画が家であることを表す。
・g : その区画が魚屋であることを表す。
・. : その区画が道であることを表す。
・# : その区画が塀であることを表す。
・高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
・与えられた街の外を通ることはできない。
・s と g はそれぞれ 1 つずつ与えられる。

解答例

# 深さ優先探索

from collections import deque

INF = int(1e9)

# 入力
h, w = map(int,input().split())
C = [] # 迷路の文字配列
for i in range(h):
    C.append(input())

# スタート、ゴールの探索
for y in range(h):
    for x in range(w):
        if C[y][x] == "s": # スタート座標はsx,sy
            sx = x
            sy = y
        if C[y][x] == "g": # ゴール座標はgx,gy
            gx = x
            gy = y

# 各座標への最短距離の配列（INFで初期化）
D = [[INF] * w for i in range(h)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# スタートからゴールへの最短距離を求める
def dfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    D[sy][sx] = 0 # スタート地点の距離を0とする

    # キューが空になるまで探索
    while len(que) != 0:
        p = que.pop() # 後入れのキューの要素を取り出す
        if p[0] == gy and p[1] == gx: # ゴールなら探索終了
            break
        for i in range(4): # pから4方向に移動 移動後の点は(nx,ny)
            ny = p[0] + dx[i]
            nx = p[1] + dy[i]
            # 移動可能か、訪れたことがあるかの判定
            if 0 <= nx < w and 0 <= ny < h and C[ny][nx] != "#" and D[ny][nx] == INF:
                # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する
                que.append([ny,nx])
                D[ny][nx] = D[p[0]][p[1]] + 1
    return D[gy][gx]

res = dfs()
if res != INF:
    print("Yes")
else:
    print("No")

解説

スタート地点からゴール地点まで道を通ってたどり着けるか答える問題です。

深さ優先探索（DFS)で解いていきます。

Cに迷路の文字列を入れていき、スタート地点の座標sx,syとゴール地点の座標gx,gyを探索します。

迷路と同じ大きさの配列Dを用意しました。。
DはINFで初期化してあり、DFSでスタート地点からの最短距離を代入していきます。

DFSは最初スタート地点をキューにプッシュします。

キューからデータを取り出し、縦横4方向に移動させた座標nx,nyを求めました。
nx,nyが迷路の範囲内で その座標が道ならキューにプッシュし、最短距離も+1して更新します。

この作業をキューが空になるまで繰り返せば、通行できる道の最短距離がすべて更新されています。
ゴール地点のDが初期のINFのままなら到着できない と判断になるので、resの値にあわせて出力すればOKです。

こんな迷路問題を解けるようになりたい、っていうのが実は蟻本の購入動機のひとつでした。
意欲的に取り組んでいきます！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

【AtCoder版！蟻本】ABC002 D - 派閥【bit全探索】

AtCoder版！蟻本のbit全探索で類題としてあげられているABC002 DをPythonで解いていきます。

リンク

atcoder.jp

AtCoder Beginner Contest 002 D - 派閥

問題文

神からの財産と、母音を取り戻した高橋くんは、AtCoder国の腐敗した政治を正すため、国会議員となろうと決めました。
もともと人心掌握術とスピーチに定評があった高橋くんは、何の苦労をすることもなく当選しました。
しかし、議員になってからが本番です。国を正すためには、首相に任命される必要があります。

AtCoder国には高橋くんを除いて N 人の国会議員と、M 個の人間関係 (x, y) が存在します。
人間関係 (x, y) とは、議員 x と議員 y が知り合いであることを意味します。
高橋くんは N 人の議員から何人かを選んで派閥を作ろうと企んでいます。
派閥に含まれるすべての議員は互いに知り合いでなければなりません。
高橋くんが作成することができる最大の派閥に属する議員数を求めるプログラムを書いてください。

制約

・N (1≦N≦12)
・M (0≦M≦N(N−1)/2)
・xi と yi はともに整数で、1 ≦ xi < yi ≦ Nを満たす。
・i≠j のとき、( xi , yi ) ≠ ( xj , yj ) であることが保証されている。

解答例

#bit全探索 組み合わせ

import itertools
n, m = map(int,input().split())

friend = [[0] * (n+1) for i in range(n+1)]
for i in range(m):
    x, y = map(int,input().split())
    friend[x][y] = 1
    friend[y][x] = 1

ans = 0
for bit in range(2**n):
    group = [] # 派閥のリスト
    for i in range(n):
        if (bit >> i) & 1:
            group.append(i+1) # bitが1ならiさんを派閥にくわえる
    # 派閥の人が互いに知り合いか判定フラグ
    flag = 1
    for j in itertools.combinations(group,2):
        if friend[j[0]][j[1]] == 0:
            flag = 0
            break
    if flag == 1:
        ans = max(ans,len(group))

print(ans)

解説

問題文の3行くらいはあまり読む意味がないですが…(^_^;)
N人の議員がいて 互いが知り合いなら派閥に入れます。
最大で何人の派閥が作れるか答える問題です。

N人の議員にたいしてbit全探索を行います。
bitが1の議員は派閥に入ると仮定して派閥候補リストgroupにいれます。
派閥候補が決まれば、そのリストから2人の組み合わせを試していきます。
friendリストを参照して、そのふたりが知り合いか判定します。
もし候補のすべての議員が互いに知り合いならansと比較して、大きいほうを代入していきます。

ループを抜けてansを出力すればACでした！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

【AtCoder版！蟻本】ARC029 A - 高橋君とお肉【bit全探索】

AtCoder版！蟻本のbit全探索で類題としてあげられているARC029 A - 高橋君とお肉をPythonで解いていきます。

リンク

atcoder.jp

AtCoder Regular Contest 029 A - 高橋君とお肉

問題文

高橋君は友達とキャンプに行くことになった。
高橋君と友達は性能が同じである 2 個の肉焼き器を持っており、それぞれの肉焼き器にお肉を乗せて並行して焼くことができる。一旦肉焼き器にお肉を乗せたら、お肉が焼きあがるまではその肉焼き器からお肉を取り出したり、その肉焼き器に別のお肉を乗せたりはできない。お肉が焼けたらお肉を取り出すことができる。
2 つの肉焼き器にまたがって 1 つのお肉を置くことはできない。また、お肉は全部で N 個あり、お肉には 1 から N まで番号が付けられている。お肉 i を焼くのには、どちらの肉焼き器でも時間 ti だけかかる。お肉を肉焼き器に置く動作、取り出す動作には時間がかからない。

高橋君はお肉を焼く係であり、N 個すべてのお肉を焼くことになった。みんなお腹が空いているので、すべてのお肉を焼くのにかかる時間を最小化させたい。
すべてのお肉を焼くのにかかる時間の最小値を求めよ。

制約

・N(1≦N≦4)
・ti(1≦ti≦50)

解答例

# bit全探索

n = int(input())

T = []
for i in range(n):
    T.append(int(input()))

ans = 1e5
for bit in range(2**n):
    time1 = 0 # 肉焼き器1号で焼き終わる時間
    time2 = 0 # 肉焼き器2号で焼き終わる時間
    for i in range(n):
        if (bit >> i) & 1: # bitが1なら1号で焼く
            time1 += T[i]
        else:
            time2 += T[i]
    tmp = max(time1,time2)
    ans = min(ans,tmp)

print(ans)

解説

2つの肉焼き器を使ってすべての肉を最も早く焼くのにかかる時間を答える問題です。

この問題もbit全探索をもちいて、bitが1の場合は肉焼き器1号で 0のときは2号で焼くことを想定しています。
各肉焼き器で必要な時間は、その機械で焼く肉の焼き上がり時間を足し合わせたものなので、1号はtime、2号はtime2にそれぞれ足し合わせました。

time1とtime2の大きいほうが その振り分けの焼き上がり終える時間になるので、ans変数と比較して小さければ その値を代入します。

ループを抜けたあとにans変数を出力すればACです！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

【AtCoder版！蟻本】ABC104 C - All Green【bit全探索】

AtCoder版！蟻本のbit全探索で類題としてあげられているABC104 CをPythonで解いていきます。

リンク

atcoder.jp

AtCoder Beginner Contest 104 C - All Green

問題文

プログラミングコンペティションサイト AtCode は、アルゴリズムの問題集を提供しています。 それぞれの問題には、難易度に応じて点数が付けられています。 現在、
1 以上 D 以下のそれぞれの整数 i に対して、100i 点を付けられた問題が pi 問存在します。 これらの p1+…+pD 問が AtCode に収録された問題のすべてです。
AtCode のユーザーは 総合スコア と呼ばれる値を持ちます。 ユーザーの総合スコアは、以下の 2 つの要素の和です。
基本スコア: ユーザーが解いた問題すべての配点の合計です。
コンプリートボーナス: 100i 点を付けられた pi 問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナス ci 点を獲得します (1≤i≤D)。
AtCode の新たなユーザーとなった高橋くんは、まだ問題を 1 問も解いていません。 彼の目標は、総合スコアを G 点以上にすることです。 このためには、少なくとも何問の問題を解く必要があるでしょうか？

制約

・1≤D≤10
・1≤pi≤100
・100≤ci≤10^6
・100≤G
・入力中のすべての値は整数である。
・ci,G はすべて 100 の倍数である。
・総合スコアを G 点以上にすることは可能である。

解答例

# bit全探索、貪欲法
D, G = map(int,input().split())

P = []
C = []
for i in range(D):
    p, c = map(int,input().split())
    P.append(p)
    C.append(c)

#最小の回答数
ans = 1e9
for bit in range(2**D): # bit 1で問題コンプリート
    total = 0 # 合計得点
    num = 0 # 回答数
    for i in range(D):
        if (bit >> i) & 1:
            total += 100 * (i+1) * P[i] + C[i]
            num += P[i]
    if total >= G: # 問題コンプリートだけでGを超える場合
        ans = min(ans,num)
    else:
        for j in reversed(range(D)): # 得点が大きいほうから貪欲法
            if (bit >> j) & 1: # コンプリートは飛ばす
                continue
            target = G - total
            if target <= P[j] * (100 * (j+1)): # 問題を解くとtotalがGを超える場合
                num += -(-target // (100 * (j+1))) # 切り上げ！
                ans = min(ans,num)
                break
            else:
                total += 100 * (j+1) * P[j]
                num += P[j]

print(ans)

解説

総合スコアを G 点以上にするために最小の問題数を答える問題です。
総合スコアは1問解くごとにもらえる基本スコア（例：A問題なら100点、B問題なら200点）と、コンプリートボーナス（例：A問題すべて解くとc1点）の合計です。

問題をすべて解く難易度の組み合わせをbit全探索し、G点を超えなかったら配点が高い問題から貪欲に解いていく方針です。

合計得点をtotal、問題の回答数をnumとおき、bitが1ならその難易度の問題をすべて解いたことにしました。
得点はその難易度の配点×問題数とコンプリートボーナスを足し合わせた値です。
もし、コンプリートだけでG点以上になった場合は、解答となるansと比較して小さければ代入します。

コンプリートだけでG点に満たなかった場合は、bit情報を用いてコンプリートしていない問題を配点の高い順に解いていくシミュレーションをしました。
この貪欲法でコンプリートしてもボーナスを考慮していません。
その場面はbit全探索でカバーされるはずなので最終的な解答には影響がないと思います。

この探索を終えてans変数を出力すればACでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク

【AtCoder版！蟻本】AOJ 0529 Darts【準備編】

AtCoder版！蟻本の準備編で類題としてあげられているAOJ0529をPythonで解いていきます。
この解答例は制限時間オーバーしてしまいますが参考のため記事にしました。

リンク

AOJ 0529 Darts

AOJ 0529 Darts

問題文

あなたは以下のルールでダーツゲームをすることになった.

あなたは,矢を的(まと)に向かって 4 本まで投げることができる.必ずしも 4 本全てを投げる必要はなく,1 本も投げなくてもかまわない.的は N 個の部分に区切られていて,各々の部分に点数 P1,..., PN が書か れている.矢が刺さった場所の点数の合計 S があなたの得点の基礎となる.S があらかじめ決められたある点数 M 以下の場合は S がそのままあなたの得点となる.しかし,S が M を超えた場合はあなたの得点は 0 点となる.

的に書かれている点数と M の値が与えられたとき,あなたが得ることのできる点数の最大値を求めるプログラムを作成せよ.

解答例

import bisect

while True:
    n, m = map(int,input().split())
    if n == 0 and m == 0:   # 終了条件
        break
    # 的の点数
    P = []
    for i in range(n):
        P.append(int(input()))
    
    # 投げない選択肢を足す
    P.append(0)
    
    # 2投で取り得る点数
    S = []
    for i in range(n + 1):
        for j in range(i,n + 1):
            S.append(P[i] + P[j])
    
    # 二分探索のためソート
    S.sort()
    # Sの要素のうちm以下の最大値の位置+1
    num = bisect.bisect_left(S,m)
    # m以上のSの要素を除外
    if num < len(S):
        if S[num] == m:
            print(m)
            continue
        S = S[:num]

    # 取り得る最大の得点
    res = 0

    # 最大の得点を探索
    for i in range(len(S)):
        tmp = bisect.bisect_left(S,m - S[i])
        res = max(res,S[i] + S[tmp-1])
        if res == m:
            break
    print(res)

解説

4投まで行うことのできるダーツで、最大何点とることができるか答える問題です。

4重ループでは完全に間に合わなくなるので、2投で取り得る点数をリストSに入れていく半分全列挙を用いました。
計算量を減らすためリストSの要素のうちmより大きい値は除外しておきます。（結果的に間に合いませんでしたが (^_^;)

最後に最大の得点を探索です。
2投した得点をきめたあと、mに最も近くなるようなSの値を二分探索で求めます。
合計得点をresと比較して、大きければresを更新していく方針です。

残念ながらこの方法は制限時間オーバーでしたが、半分全列挙・二分探索を使用した例として記事に残します。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク