[백준] 2178 미로 탐색, python, C

www.acmicpc.net/problem/2178

2178번: 미로 탐색

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [input() for _ in range(N)]
visit = [[0] * M for _ in range(N)]

def bfs(r, c):
    q = deque()
    q.append((r, c))
    visit[r][c] = 1
    delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        x, y = q.popleft()
        for i in range(4):
            dx = x + delta[i][0]
            dy = y + delta[i][1]
            if 0 > dx or dx >= N or 0 > dy or dy >= M: continue
            if matrix[dx][dy] == '0': continue
            if visit[dx][dy]: continue
            visit[dx][dy] = visit[x][y] + 1
            q.append((dx, dy))

bfs(0, 0)
print(visit[N-1][M-1])

bfs를 사용해서 최소거리를 찾는 문제이다

가장 기본적인 2차원 bfs이므로 설명은 안하고 넘어간다.

---

 

#include <stdio.h>

int maze[101][101];
int visit[101][101] = { 0, };
int xx[] = { 0,1,0,-1 };
int yy[] = { 1,0,-1,0 };
int n, m;
int front = -1, rear =-1;

struct node
{
	int x;
	int y;
};
struct node queue[10001];
void push(int x, int y)
{
	rear=(rear+1)%10001;
	queue[rear].x = x;
	queue[rear].y = y;
}
struct node pop()
{
	front = (front + 1) % 10001;
	return queue[front];
}

void bfs(int x, int y)
{
	struct node temp;
	push(x, y);
	int nx, ny;
	while(front!=rear)
	{
		temp=pop();
		x = temp.x;
		y = temp.y;
		for(int i=0;i<4;i++)
		{
			
			nx = x + xx[i];
			ny = y + yy[i];
			if (nx>=1&&ny>=1&&ny<=m&&nx<=n&&visit[nx][ny] == 0 && maze[nx][ny] == 1)
			{
				visit[nx][ny] = visit[x][y] + 1;
				push(nx, ny);
			}

		}
	}
	return;
}
int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			scanf("%1d", &maze[i][j]);
		}
	}
	visit[1][1] = 1;
	bfs(1, 1);
	printf("%d", visit[n][m]);
}

C를 공부하기 위해 타인의 코드를 가져왔다.

main과 bfs는 파이썬이랑 비슷하니 넘어가고 구조체를 만들어서 원형 queue를 구현했다.