C++)
#include <iostream>
#include <queue>
#define MAX_NUM 102
using namespace std;
char arr[MAX_NUM][MAX_NUM];
int visited[MAX_NUM][MAX_NUM];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> q;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
visited[0][0] = 1;
q.push({ 0,0 });
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (arr[nx][ny] == '1' && visited[nx][ny] == 0) {
q.push({ nx,ny });
visited[nx][ny] = visited[x][y] + 1;
}
}
}
cout << visited[n - 1][m - 1];
return 0;
}
Python)
import sys
from collections import deque
read = sys.stdin.readline
dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()
n, m = map(int, read().rstrip().split())
arr = [''] * n
visited = [ [-1] * m for _ in range(n) ]
for i in range(n):
arr[i] = list(map(int, read().rstrip()))
visited[0][0] = 1
q.append((0,0))
while q:
x, y = q.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if arr[nx][ny] == 1 and visited[nx][ny] == -1:
visited[nx][ny] = visited[x][y] + 1
q.append((nx,ny))
print(visited[n-1][m-1])'백준 2 > 그래프' 카테고리의 다른 글
| [백준 9328] 열쇠 (0) | 2020.12.08 |
|---|---|
| [백준 11403] 경로 찾기 (0) | 2020.12.08 |
| [백준 2667] 단지 번호 붙이기 (C++/Python) (0) | 2020.12.08 |
| [백준 7569] 토마토 (C++/Python) (0) | 2020.12.08 |
| [백준 7576] 토마토 (C++/Python) (0) | 2020.12.08 |