백준 14940 쉬운 최단거리 파이썬, C++

리뷰

BFS를 통한 풀이 문제

 

문제 풀이

1. 리스트1에 입력 값을 받고, 리스트2에 출력할 2차원 배열을 n * m만큼 -1로 초기화 한다. 방향 배열을 초기화 한다.
2. 리스트1에 존재하는 0값을 찾아 리스트2의 동일한 위치를 0으로 만들어 준다.
3. 리스트1에 존재하는 2값을 찾아 시작점을 나타낼 좌표로 저장을 한다.
4. 시작 좌표를 기준으로 bfs를 시작한다, 범위를 벗어나지 않으며 다음 좌표의 ans 값이 -1일 경우 현재 위치의 값에 1을 더한 값을 다음 좌표에 할당해 주고 큐에 다음 좌표를 추가한다.
5. bfs가 종료된 이후 리스트2 배열의 전체를 출력해 주면 된다.

 

참고 사항

방문 배열은 딱히 사용할 필요가 없었다.

 

 

정답 코드

파이썬 코드

import sys, collections

n, m = map(int, sys.stdin.readline().split())
lst = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
ans = [[-1] * m for _ in range(n)]
start = tuple()
for i in range(n):
    for j in range(m):
        if lst[i][j] == 2:
            start = (i, j)
        if lst[i][j] == 0:
            ans[i][j] = 0
dist = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def bfs(start):
    q = collections.deque([start])
    ans[start[0]][start[1]] = 0
    while q:
        x, y = q.popleft()
        for dx, dy in dist:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and ans[nx][ny] == -1:
                ans[nx][ny] = ans[x][y] + 1
                q.append((nx, ny))


bfs(start)
for i in range(n):
    print(*ans[i])

 

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

int n, m;
vector<vector<int>> lst;
vector<vector<int>> ans;
vector<pair<int, int>> dist = { {1,0}, {-1,0}, {0, 1}, {0, -1} };

void bfs(queue<pair<int, int>> q) {
	ans[q.front().first][q.front().second] = 0;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < dist.size(); i++) {
			int nx = x + dist[i].first;
			int ny = y + dist[i].second;
			if (0 <= nx && nx < n && 0 <= ny && ny < m && ans[nx][ny] == -1) {
				ans[nx][ny] = ans[x][y] + 1;
				q.push({ nx, ny });
			}
		}
	}
}

int main() {
	cin >> n >> m;
	lst.resize(n, vector<int>(m));
	ans.resize(n, vector<int>(m, -1));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> lst[i][j];
		}
	}
	queue<pair<int, int>> start;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == 2) {
				start.push({ i, j });
			}
			if (lst[i][j] == 0) {
				ans[i][j] = 0;
			}
		}
	}
	bfs(start);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << ans[i][j] << " ";
		}
		cout << "\n";
	}
}