BOJ / 2178번 / 미로 탐색 [Go][Python3]

👩🏻‍💻 문제

2178번: 미로 탐색

---

✍🏻 풀이

🎨 Go

// https://www.acmicpc.net/problem/2178
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

var (
	graph   [][]string
	count   [][]int
	rowDiff = []int{0, 0, -1, 1}
	colDiff = []int{-1, 1, 0, 0}
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, m int
	fmt.Fscanln(reader, &n, &m)

	count = make([][]int, n)
	for i := 0; i < n; i++ {
		count[i] = make([]int, m)
	}

	for i := 0; i < n; i++ {
		input, _ := reader.ReadString('\n') // 공백 포함하여 입력 받기 위해 ReadString() 사용
		inputs := strings.Split(strings.ReplaceAll(input, "\n", ""), "")
		graph = append(graph, inputs)
	}

	bfs(0, 0)
	fmt.Fprintln(writer, count[n-1][m-1])
}

type pos struct {
	row int
	col int
}

func bfs(row, col int) { // 최단 경로 구할 때 BFS 활용
	queue := []pos{pos{row, col}}
	count[row][col] = 1
	for len(queue) > 0 {
		r := queue[0].row
		c := queue[0].col
		if r == len(graph) && c == len(graph[0]) {
			break
		}
		if len(queue) == 1 {
			queue = []pos{}
		} else {
			queue = queue[1:]
		}

		for i := 0; i < 4; i++ {
			newRow := r + rowDiff[i]
			newCol := c + colDiff[i]
			if check(newRow, newCol) {
				queue = append(queue, pos{newRow, newCol})
				count[newRow][newCol] = count[r][c] + 1
			}
		}
	}
}

func check(row, col int) bool {
	if row >= len(graph) || row < 0 || col >= len(graph[0]) || col < 0 {
		return false
	}
	if graph[row][col] == "0" || count[row][col] != 0 {
		return false
	}
	return true
}

🎨 Python3

# https://www.acmicpc.net/problem/2178
import sys

count = []
graph = []
row_diff = [0, 0, -1, 1]
col_diff = [-1, 1, 0, 0]

def check(row, col):
    global graph
    if row >= len(graph) or row < 0 or col >= len(graph[0]) or col < 0:
        return False
    if graph[row][col] == 0 or count[row][col] != 0:
        return False
    return True

def bfs(row, col):
    global count
    global graph
    queue = [(row, col)]
    count[row][col] = 1
    while len(queue) > 0:
        r = queue[0][0]
        c = queue[0][1]
        if r == len(graph) and c == len(graph[0]):
            break
        queue.pop(0)

        for i in range(4):
            new_row = r + row_diff[i]
            new_col = c + col_diff[i]
            if check(new_row, new_col):
                queue.append((new_row, new_col))
                count[new_row][new_col] = count[r][c] + 1

if __name__ == "__main__":
    n, m = list(map(int, sys.stdin.readline().split()))
    count = [[0 for i in range(m)] for j in range(n)]
    graph = []

    for i in range(n):
        inputs = list(map(int, list(sys.stdin.readline().rstrip())))
        graph.append(inputs)

    bfs(0, 0)
    print(count[n-1][m-1])