⛳
アルゴリズムを実践的に学びたい場合、競技プログラミングの問題を2度解こう
はじめに
この記事では、アルゴリズムの学習のために競技プログラミングの問題を解く場合におすすめの、問題の解き方について書いていきます。タイトルにもある通り、2度解くことがおすすめです。その理由についてこれから解説していきます。
なお、解説に使用しているプログラミング言語はJavaとなります。
一応、前回私が書いた記事の続きの話となっているので、リンクを貼り付けておきます。読まなくても特に問題はありません。
アルゴリズムの知識がない状態でAtCoderの問題を解いて勉強する方法
初見の問題を解いた時の状態
初見の問題を解いた時のソースコードは、例えば以下のような状態になります。(使用した問題はAtCoderのABC387のD問題です。)
実際に初見で解いたソースコード(java)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
private static int h;
private static int w;
private static char[][] chars;
private static int[] start = new int[2];
private static int[] goal = new int[2];
private static int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public static void main(String[] args) {
var sc = new Scanner(System.in);
h = sc.nextInt();
w = sc.nextInt();
var strings = new String[h];
for (int i = 0; i < h; i++) {
strings[i] = sc.next();
}
sc.close();
// 文字列の配列をcharの2次元配列にする。
chars = new char[h][w];
for (int i = 0; i < h; i++) {
chars[i] = strings[i].toCharArray();
}
// スタート位置とゴール位置を特定する。
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (chars[i][j] == 'S') {
start[0] = i;
start[1] = j;
} else if (chars[i][j] == 'G') {
goal[0] = i;
goal[1] = j;
}
}
}
var result = bfs();
System.out.println(result);
}
private static int bfs() {
int result = 0;
// スタート地点で左右に行く場合をi = 0, 上下に行く場合をi = 1とする。
for (int i = 0; i < 2; i++) {
Queue<int[]> queue = new LinkedList<>();
queue.add(newIntArray(start[0], start[1], 0));
// 既に訪れた地点にtrueを入れて記録する。
var visitedPlace = new boolean[h][w];
visitedPlace[start[0]][start[1]] = true;
// // スタートからの移動距離。(デバッグ用)
// // 配列を初期化すると全ての要素に0が入るので、スタート位置の距離を1として、最後に1を引くこととする。
// var distances = new int[h][w];
// distances[start[0]][start[1]] = 1;
while (!queue.isEmpty()) {
int[] currentLocation = queue.poll();
var y = currentLocation[0];
var x = currentLocation[1];
var distance = currentLocation[2];
if (y == goal[0] && x == goal[1]) {
if (result == 0) {
result = distance;
} else {
result = Math.min(result, distance);
}
}
// 縦移動の場合は上移動がj = 0, 下移動がj = 1
// 横移動の場合は右移動がj = 0, 左移動がj = 1
for (int j = 0; j < 2; j++) {
int nextY;
int nextX;
// 縦移動か横移動か制約を確認し、次の地点を調べる。
if ((i + distance) % 2 == 0) {
nextY = y + move[j][0];
nextX = x + move[j][1];
} else {
nextY = y + move[j + 2][0];
nextX = x + move[j + 2][1];
}
// 道ではない場合false
var flag = nextY < h && nextY >= 0 && nextX < w && nextX >= 0;
if (flag && chars[nextY][nextX] == '#') {
flag = false;
}
// 既に訪れた場所には進まない
if (flag && visitedPlace[nextY][nextX]) {
flag = false;
}
// 進める道であれば、次の探索地点をqueueに加える。
if (flag) {
queue.add(newIntArray(nextY, nextX, distance + 1));
visitedPlace[nextY][nextX] = true;
// デバッグ用
// distances[nextY][nextX] = distance + 1;
}
}
}
}
return result == 0 ? -1 : result;
}
private static int[] newIntArray(Integer y, Integer x, Integer distance) {
return new int[]{y, x, distance};
}
}
この問題はBFS(幅優先探索)を用いて、特定の条件下でスタートからゴールまでの最短経路を求める問題です。
これでもAtCoderの平均的な解答と比べるとソースコードは綺麗な方だと思っていますが、見にくい部分はあります。特に以下のfor文の部分はごちゃごちゃしていて、何をやっているのか分かりにくいでしょう。
ごちゃごちゃしている部分
// 縦移動の場合は上移動がj = 0, 下移動がj = 1
// 横移動の場合は右移動がj = 0, 左移動がj = 1
for (int j = 0; j < 2; j++) {
int nextY;
int nextX;
// 縦移動か横移動か制約を確認し、次の地点を調べる。
if ((i + distance) % 2 == 0) {
nextY = y + move[j][0];
nextX = x + move[j][1];
} else {
nextY = y + move[j + 2][0];
nextX = x + move[j + 2][1];
}
// 道ではない場合false
var flag = nextY < h && nextY >= 0 && nextX < w && nextX >= 0;
if (flag && chars[nextY][nextX] == '#') {
flag = false;
}
// 既に訪れた場所には進まない
if (flag && visitedPlace[nextY][nextX]) {
flag = false;
}
// 進める道であれば、次の探索地点をqueueに加える。
if (flag) {
queue.add(newIntArray(nextY, nextX, distance + 1));
visitedPlace[nextY][nextX] = true;
// デバッグ用
// distances[nextY][nextX] = distance + 1;
}
}
このソースコードを綺麗にするために、改めて1から問題を解き直します。
問題を解き直すメリット
問題を解き直すメリットは、ソースコードを綺麗にできるだけではありません。頭の中で解き方を整理した状態で改めて解くことで、次のような効果が期待できます。
- 解き方の理解がさらに深まる
- 応用が効くようになる
- 記憶として定着しやすい
効率の良い学習方法だと考えられるので、私は解説なしで解けなかった問題では2回解くようにしています。
ソースコードを綺麗にする方法
では実際に問題を解き直すにあたって、どのようにしてソースコードを綺麗にすればよいでしょうか。綺麗にする上でいくつかポイントがあります。
先にソースコードを綺麗にした結果を貼り付けておきます。
綺麗にしたソースコード
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
private static int h;
private static int w;
// 文字列配列をcharの2次元配列に変換したもの
private static char[][] chars;
private static final int[] start = new int[2];
private static final int[] goal = new int[2];
public static void main(String[] args) {
// 標準入力の文字列を格納する。
String[] strings = input();
// 文字列配列をcharの2次元配列にする。
chars = createMap(strings);
// スタートとゴールを記録する。
recordStartAndGoal();
// 幅優先探索で経路を求める。
Integer result = bfs();
System.out.println(result);
}
// 標準入力の情報を格納し、文字列配列を返す。
private static String[] input() {
var sc = new Scanner(System.in);
h = sc.nextInt();
w = sc.nextInt();
var strings = new String[h];
for (int i = 0; i < h; i++) {
strings[i] = sc.next();
}
sc.close();
return strings;
}
private static char[][] createMap(String[] strings) {
var chars = new char[h][w];
for (int i = 0; i < h; i++) {
chars[i] = strings[i].toCharArray();
}
return chars;
}
private static void recordStartAndGoal() {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
switch (chars[i][j]) {
case 'S' -> {
start[0] = i;
start[1] = j;
}
case 'G' -> {
goal[0] = i;
goal[1] = j;
}
default -> {
}
}
}
}
}
private static Integer bfs() {
var move = new Move();
var result = 0;
// 最初が縦移動の場合(parity = 0)と横移動の場合(parity = 1)両方を計算する。
for (int parity = 0; parity < 2; parity++) {
// 探索する場所を記録するキュー。
Queue<int[]> queue = new LinkedList<>();
queue.add(createQueueElements(start[0], start[1], 0));
// 既に探索した場所をtrueとして記録する。
var visitedPlace = new boolean[h][w];
visitedPlace[start[0]][start[1]] = true;
while (!queue.isEmpty()) {
int[] currentInfo = queue.poll();
var currentRow = currentInfo[0];
var currentColumn = currentInfo[1];
var currentDistance = currentInfo[2];
// ゴール地点に到達したら距離を記録する。
if (currentRow == goal[0] && currentColumn == goal[1]) {
result = result == 0 ? currentDistance : Math.min(currentDistance, result);
break;
}
int[][] direction = move.direction(move.isVertical(currentDistance, parity));
// 左右または上下の2方向を調べ、道があれば次に探索する場所としてqueueに追加する。
for (int i = 0; i < 2; i++) {
var nextRow = currentRow + direction[i][0];
var nextColumn = currentColumn + direction[i][1];
// 正しい道のりである場合、探索する地点をqueueに入れておく。
if (isValidPath(chars, visitedPlace, nextRow, nextColumn)) {
queue.add(createQueueElements(nextRow, nextColumn, currentDistance + 1));
visitedPlace[nextRow][nextColumn] = true;
}
}
}
}
return result == 0 ? -1 : result;
}
private static int[] createQueueElements(Integer r, Integer c, Integer distance) {
return new int[]{r, c, distance};
}
private static boolean isValidPath(char[][] chars, boolean[][] visitedPlace, Integer r, Integer c) {
// 場外に出てはいけない。
var flag = r >= 0 && r < h && c >= 0 && c < w;
// '#'に進んではいけない。
if (flag && chars[r][c] == '#') {
flag = false;
}
// 既に通った場所に戻らない。
if (flag && visitedPlace[r][c]) {
flag = false;
}
return flag;
}
// 進む方向を定義するクラス。
private static class Move {
private final int[][] moveVertical = {{1, 0}, {-1, 0}};
private final int[][] moveHorizontal = {{0, 1}, {0, -1}};
public int[][] direction(boolean isVertical) {
return isVertical ? moveVertical : moveHorizontal;
}
public boolean isVertical(Integer distance, Integer parity) {
return (distance + parity) % 2 == 0;
}
}
}
行数は30行ほど多くなっていますが、見やすさはかなり違っていると思います。
呼び出し元となる関数(main関数)には極力コードを書かない
大本の呼び出し元の関数にはあまりコードを書かない方が、全体像が見えやすくなって綺麗になります。
例として、Javaのmain関数はこのくらい行数を減らして良いです。
短くまとめたmain関数
public static void main(String[] args) {
// 標準入力の文字列を格納する。
String[] strings = input();
// 文字列配列をcharの2次元配列にする。
chars = createMap(strings);
// スタートとゴールを記録する。
recordStartAndGoal();
// 幅優先探索で経路を求める。
Integer result = bfs();
System.out.println(result);
}
分かりにくいデータの持ち方になる場合、クラスを定義する
初見で解いた時のソースコードで特に分かりにくかった部分は、このif文のところでしょう。
特に分かりにくいif文
// 縦移動か横移動か制約を確認し、次の地点を調べる。
if ((i + distance) % 2 == 0) {
nextY = y + move[j][0];
nextX = x + move[j][1];
} else {
nextY = y + move[j + 2][0];
nextX = x + move[j + 2][1];
}
縦移動と横移動を交互に行うという制約に合わせるためにこのような書き方になっていますが、以下のようにmoveという配列が何を表現しているのかも分かりにくい状況となっています。
private static int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
このように扱うデータがそもそも何を表しているか分かりにくくなる場合、クラスを定義し、処理や変数に名前を付けることでコードの意図を理解しやすくしてみましょう。
試しにMoveというクラスを定義すると、次のようになります。
Moveクラス
// 進む方向を定義するクラス。
private static class Move {
private final int[][] moveVertical = {{1, 0}, {-1, 0}};
private final int[][] moveHorizontal = {{0, 1}, {0, -1}};
public int[][] direction(boolean isVertical) {
return isVertical ? moveVertical : moveHorizontal;
}
public boolean isVertical(Integer distance, Integer parity) {
return (distance + parity) % 2 == 0;
}
}
上下方向に移動するための変数と水平方向に移動するための変数を別々に定義しています。directionという関数を使うと、条件に合わせて適切な方の変数を渡すようになっています。また、その条件を判定するためのisVerticalという関数を定義することで、どういう情報(変数)を入れれば条件を判定できるかが明確になっています。
このようなMoveというクラスを定義することで、先ほどの分かりにくいif文は以下のようになります。結果としてif文すら消えてしまいました。
特に分かりにくいif文を改善したもの
int[][] direction = move.direction(move.isVertical(currentDistance, parity));
// 左右または上下の2方向を調べ、道があれば次に探索する場所としてqueueに追加する。
for (int i = 0; i < 2; i++) {
var nextRow = currentRow + direction[i][0];
var nextColumn = currentColumn + direction[i][1];
if文が連続する部分は1つにまとめる
以下のようにif文が連続する部分も、ソースコードが分かりにくくなる一因です。
if文が連続している部分
// 道ではない場合false
var flag = nextY < h && nextY >= 0 && nextX < w && nextX >= 0;
if (flag && chars[nextY][nextX] == '#') {
flag = false;
}
// 既に訪れた場所には進まない
if (flag && visitedPlace[nextY][nextX]) {
flag = false;
}
// 進める道であれば、次の探索地点をqueueに加える。
if (flag) {
queue.add(newIntArray(nextY, nextX, distance + 1));
visitedPlace[nextY][nextX] = true;
// デバッグ用
// distances[nextY][nextX] = distance + 1;
}
このような連続するif文は、やりたいことや処理の意味合いが似ている場合が多いので、極力1つにまとめてしまいましょう。
if文を1つの関数(isValidPath)にまとめたもの
private static boolean isValidPath(char[][] chars, boolean[][] visitedPlace, Integer r, Integer c) {
// 場外に出てはいけない。
var flag = r >= 0 && r < h && c >= 0 && c < w;
// '#'に進んではいけない。
if (flag && chars[r][c] == '#') {
flag = false;
}
// 既に通った場所に戻らない。
if (flag && visitedPlace[r][c]) {
flag = false;
}
return flag;
}
処理と変数に名前を付けられるという意味で、似たような処理を関数化することは、コードの可読性の向上に大いに役立ちます。
その他
他にもコーディングをする上で注意すべき点はいくつかありますが、本題とは逸れるのでここでは割愛します。気になった方はコーディングに関する書籍などで学習したり、業務でコーディングが綺麗な人を真似したりしてみましょう。
改めて解答の中核(bfs関数)となるコードを確認し、順番に処理を追ってみる
それでは、解答の中核であるbfs関数について、改めて綺麗にした後のコードを見ていきます。
綺麗にしたbfs関数
private static Integer bfs() {
var move = new Move();
var result = 0;
// 最初が縦移動の場合(parity = 0)と横移動の場合(parity = 1)両方を計算する。
for (int parity = 0; parity < 2; parity++) {
// 探索する場所を記録するキュー。
Queue<int[]> queue = new LinkedList<>();
queue.add(createQueueElements(start[0], start[1], 0));
// 既に探索した場所をtrueとして記録する。
var visitedPlace = new boolean[h][w];
visitedPlace[start[0]][start[1]] = true;
while (!queue.isEmpty()) {
int[] currentInfo = queue.poll();
var currentRow = currentInfo[0];
var currentColumn = currentInfo[1];
var currentDistance = currentInfo[2];
// ゴール地点に到達したら距離を記録する。
if (currentRow == goal[0] && currentColumn == goal[1]) {
result = result == 0 ? currentDistance : Math.min(currentDistance, result);
break;
}
int[][] direction = move.direction(move.isVertical(currentDistance, parity));
// 左右または上下の2方向を調べ、道があれば次に探索する場所としてqueueに追加する。
for (int i = 0; i < 2; i++) {
var nextRow = currentRow + direction[i][0];
var nextColumn = currentColumn + direction[i][1];
// 正しい道のりである場合、探索する地点をqueueに入れておく。
if (isValidPath(chars, visitedPlace, nextRow, nextColumn)) {
queue.add(createQueueElements(nextRow, nextColumn, currentDistance + 1));
visitedPlace[nextRow][nextColumn] = true;
}
}
}
}
return result == 0 ? -1 : result;
}
コードを上から追ってみて、他の人に順を追って説明できそうだったり、ブログ記事で説明できるような状態であればOKです。そこまでできれば、この問題で学んだアルゴリズムの理解は十分だと言えるでしょう。
コードを綺麗にする作業は完璧にする必要はありません。こだわり過ぎて時間をかけすぎるのも良くないので、適当な所で切り上げましょう。
おわりに
この記事では、アルゴリズムを実践的に学習する場合の、競技プログラミングの問題のおすすめの解き方について書きました。
アルゴリズムに限らず、何らかのことを学習する際は、以下のことを意識すると学習効率が上がります。
- まず問題を解く
- 解けなかった問題について、解くのに必要だった前提知識を学ぶ
- 綺麗に(セオリー通り)問題を解き直す
- 自分の言葉で説明できるようにする(人に教える・記事で説明するなど)
逆に言うと、アルゴリズムの学習方法も他の分野の学習方法と同じです。上記のことを意識して学習してみてはいかがでしょうか。
Discussion