この記事では
プログラミング学習サービスpaizaラーニングの
スキルチェックレベルアップ問題集をわかりやすく解説します！
プログラミング言語はpythonです。
今回はSランク相当の以下の問題を解説します。
他のレベルアップ問題集の解答と解説も紹介しているので
ぜひご参考ください！
またpaizaの各ランクの攻略法は
こちらで詳しく紹介しているので、ぜひご参考ください！
この問題を解くための3つのポイント
まずは「この問題を解くためのポイント」をご説明します。
問題はこちらからご確認ください。
この問題を解くためのポイントは以下の3つです。
- 島を探す
- 島の大きさを確認
- 外枠でのエラーを無くす
島を探す
まずは「島を探す」です。
今回の問題では入力された表の中で
"1"が隣接している塊を島としてカウントします。
そのため最初に表のそれぞれの値が"1"なのか判定しなければなりません。
今回は表の左上から右下に進んで調べていくため
列と行に関してfor文を使用します。
''' colが列数、rowが行数 '''
# 各行に対して繰り返す
for i in range(row):
# 各列に対して繰り返す
for j in range(col):for文については、こちらをご参考ください！
次にif文をで表のそれぞれの値が "1" なのかの条件を課します。
"""
map_listは以下のような2次元配列(リスト)
[
["0", "1", "1", "0"],
["1", "0", "1", "0"],
["1", "0", "0", "0"],
["0", "0", "1", "1"],
["0", "1", "1", "1"]
]
"""
''' colが列数、rowが行数 '''
# 各行に対して繰り返す
for i in range(row):
# 各列に対して繰り返す
for j in range(col):
# "1"の場合
if map_list[i][j] == "1":リストとif文については、こちらをご参考ください！
島の大きさを確認
次は「島の大きさを確認」です。
今回の問題は値が "1" の場所ではなく"1"の塊が島なので
"1"なのか判定するだけでは、同じ島を何度もカウントしてしまいます。
そのため以下の流れで島の大きさを確認します！
- 各表の値が
"1"なのか判定 "1"の場合は"0"に置換- 置換した場所に隣接する上下左右の場所の値も判定
- 隣接する上下左右の場所が
"0"になるまで2, 3の処理を繰り返す
今回は2, 3, 4の処理を1つの関数にまとめます。
# xが列、yが行
def check(x, y):
# 2. ~ 4.の処理を書く次に"1"の場所を記憶するリストを定義し、最初の場所を追加します。
# 関数を定義
def check(x, y):
# リストを定義し最初の場所を追加
lands = [[x, y]]
# "0"に置換
map_list[y][x] = "0"リストについては、こちらをご参考ください！
そして最初の場所の値を"0"に置換します。
# 関数を定義
def check(x, y):
# リストを定義し最初の場所を追加
lands = [[x, y]]
# "0"に置換
map_list[y][x] = "0"次に隣接する上下左右の場所の値が"1"なのか判定し
"1"の場合はappendメソッドを使ってリストに追加します。
# 関数を定義
def check(x, y):
# リストを定義し最初の場所を追加
lands = [[x, y]]
# "0"に置換
map_list[y][x] = "0"
# 下の場所
if map_list[y+1][x] == "1":
lands.append([x, y+1])
# 右の場所
if map_list[y][x+1] == "1":
lands.append([x+1, y])
# 上の場所
if map_list[y-1][x] == "1":
lands.append([x, y-1])
# 左の場所
if map_list[y][x-1] == "1":
lands.append([x-1, y])最後にwhile文を使って処理を繰り返します。
while文はリストの要素の座標をpopメソッドを使って
x, y に代入し、リストの要素が無くなるまで繰り返します。
# 関数を定義
def check(x, y):
# リストを定義し最初の場所を追加
lands = [[x, y]]
# landsの要素が無くなるまで繰り返す
while lands:
# 座標を更新
x, y = lands.pop()
# "0"に置換
map_list[y][x] = "0"
# 下の場所
if map_list[y+1][x] == "1":
lands.append([x, y+1])
# 右の場所
if map_list[y][x+1] == "1":
lands.append([x+1, y])
# 上の場所
if map_list[y-1][x] == "1":
lands.append([x, y-1])
# 左の場所
if map_list[y][x-1] == "1":
lands.append([x-1, y])while文については、こちらをご参考ください！
外枠でのエラーを無くす
最後は「外枠でのエラーを無くす」です。
実は「島の大きさを確認する」で紹介した関数checkでは
表の一部の場所でエラーが発生してしまいます。
# 関数を定義
def check(x, y):
# リストを定義し最初の場所を追加
lands = [[x, y]]
# landsの要素が無くなるまで繰り返す
while lands:
# 座標を更新
x, y = lands.pop()
# "0"に置換
map_list[y][x] = "0"
# 下の場所
if map_list[y+1][x] == "1":
lands.append([x, y+1])
# 右の場所
if map_list[y][x+1] == "1":
lands.append([x+1, y])
# 上の場所
if map_list[y-1][x] == "1":
lands.append([x, y-1])
# 左の場所
if map_list[y][x-1] == "1":
lands.append([x-1, y])それが表の右端や下端などの外枠です。
外枠では隣接する上下左右の場所の中で
データが存在しない部分が含まれてしまいます。
そのため外枠を"0"で囲み、エラーを回避します！
"""
旧）map_list
[
["0", "1", "1", "0"],
["1", "0", "1", "0"],
["1", "0", "0", "0"],
["0", "0", "1", "1"],
["0", "1", "1", "1"]
]
新）map_list
[
["0", "0", "0", "0", "0", "0"],
["0", "0", "1", "1", "0", "0"],
["0", "0", "1", "1", "0", "0"],
["0", "1", "0", "1", "0", "0"],
["0", "1", "0", "0", "0", "0"],
["0", "0", "0", "1", "1", "0"],
["0", "0", "1", "1", "1", "0"],
["0", "0", "0", "0", "0", "0"]
]
""""0"で囲むとエラーは回避できますが
行と列がそれぞれ2つずつ増えるので
「島を探す」で紹介したfor文の範囲を変化させなければなりません！
''' colが列数、rowが行数 '''
# 2行目からrow+1行目まで繰り返す
for i in range(1, row+1):
# 2列目からcol+1列目まで繰り返す
for j in range(1, col+1):島探し (paizaランク S 相当)の解答
ではここまで紹介したポイントを使って、問題を解いていきます。
入力を受け取り、表を準備
まずは「入力を受け取り、表を準備」です。
今回の問題では1行目で表の列数と行数が
半角スペース区切りで入力されます。
そのためsplit関数を使って2つの変数に代入し、int型に変換します。
# 表の列数と行数の入力を受け取る
col, row = input().split()
# int型に変換
col = int(col)
row = int(row)int型などの変数の型については、こちらをご参考ください！
また内包表記を使うと1行で書けるため、よりシンプルです。
# 表の列数と行数の入力を受け取り、int型に変換
col, row = [int(x) for x in input().split()]内包表記については、こちらをご参考ください！
2行目以降では各行の値が半角スペース区切りで入力されるので
リストを使って2次元配列の要素として代入します。
# 入力を代入するリストを定義
map_list = []
# 各行に対して繰り返す
for i in range(row):
# 1行分のリストを追加
map_list.append(input().split())さらに「外枠でのエラーを無くす」で紹介したように
エラー回避のため、外枠を"0"で囲みます。
# 1行目を"0"で埋める
map_list = [["0"] * (n+2)]
# 各行に対して繰り返す
for i in range(row):
# "0"で挟む
map_list.append(["0"] + input().split() + ["0"])
# 1行目と同じリストを最後の行に追加
map_list.append(map_list[0])入力については、こちらをご参考ください！
島かどうかを判定しその数をカウント
次は「島かどうかを判定しその数をカウント」です。
まずfor文とif文を使って表のそれぞれの値が"1"なのか判定します。
''' colが列数、rowが行数 '''
# 2行目からrow+1行目まで繰り返す
for i in range(1, row+1):
# 2列目からcol+1列目まで繰り返す
for j in range(1, col+1):
# "1"の場合
if map_list[i][j] == "1":次に島の大きさを確認する関数を定義し
同じ島の場所を全て"0"に置換します。
# 関数を定義
def check(x, y):
# リストを定義し最初の場所を追加
lands = [[x, y]]
# landsの要素が無くなるまで繰り返す
while lands:
# 座標を更新
x, y = lands.pop()
# "0"に置換
map_list[y][x] = "0"
# 下の場所
if map_list[y+1][x] == "1":
lands.append([x, y+1])
# 右の場所
if map_list[y][x+1] == "1":
lands.append([x+1, y])
# 上の場所
if map_list[y-1][x] == "1":
lands.append([x, y-1])
# 左の場所
if map_list[y][x-1] == "1":
lands.append([x-1, y])
''' colが列数、rowが行数 '''
# 2行目からrow+1行目まで繰り返す
for i in range(1, row+1):
# 2列目からcol+1列目まで繰り返す
for j in range(1, col+1):
# "1"の場合
if map_list[i][j] == "1":
# 島の大きさを確認し"0"に置換
check(j, i)次に島の数をカウントします。
# 島の数を数える変数
count = 0
''' colが列数、rowが行数 '''
# 2行目からrow+1行目まで繰り返す
for i in range(1, row+1):
# 2列目からcol+1列目まで繰り返す
for j in range(1, row+1):
# "1"の場合
if map_list[i][j] == "1":
# 島の大きさを確認し"0"に置換
check(j, i)
# 島をカウント
count += 1while文については、こちらをご参考ください！
最後にprint関数を使って、結果を出力します。
# 島の数を出力
print(count)出力については、こちらをご参考ください！
島探し(paizaランクS相当)の解答
まとめると「島探し(paizaランクS相当)」の解答は以下です。
# 表の列数と行数の入力を受け取り、int型に変換
col, row = [int(x) for x in input().split()]
# 1行目を"0"で埋める
map_list = [["0"] * (col+2)]
# 各行に対して繰り返す
for i in range(row):
# "0"で挟む
map_list.append(["0"] + input().split() + ["0"])
# 1行目と同じリストを最後の行に追加
map_list.append(map_list[0])
# 関数を定義
def check(x, y):
# リストを定義し最初の場所を追加
lands = [[x, y]]
# landsの要素が無くなるまで繰り返す
while lands:
# 座標を更新
x, y = lands.pop()
# "0"に置換
map_list[y][x] = "0"
# 下の場所
if map_list[y+1][x] == "1":
lands.append([x, y+1])
# 右の場所
if map_list[y][x+1] == "1":
lands.append([x+1, y])
# 上の場所
if map_list[y-1][x] == "1":
lands.append([x, y-1])
# 左の場所
if map_list[y][x-1] == "1":
lands.append([x-1, y])
# 島の数を数える変数
count = 0
''' colが列数、rowが行数 '''
# 2行目からrow+1行目まで繰り返す
for i in range(1, row+1):
# 2列目からcol+1列目まで繰り返す
for j in range(1, col+1):
# "1"の場合
if map_list[i][j] == "1":
# 島の大きさを確認し"0"に置換
check(j, i)
# 島をカウント
count += 1
# 島の数を出力
print(count)ぜひご参考ください！
まとめ
今回はpaizaのスキルチェックレベルアップ問題集の中で
- 島探し(paizaランクS相当)
の解答と解説を紹介しました。
Sランクの問題になると、まず正しい答えを出力することでさえ難しくなります。
また制限時間がかなり厳しくなってくるので
問題分の読み間違いなどの時間のロスには注意しましょう！
ぜひSランク目指してがんばってください！
また他のレベルアップ問題集の問題についての解説も、ぜひご参考ください！
