[Python][C++] 14940번 쉬운 최단거리

문제

https://www.acmicpc.net/problem/14940

 

 

 

 

코드

1. Python

import sys
from collections import deque  # BFS에서 사용할 큐를 위해 deque 라이브러리 임포트

input = sys.stdin.readline  # 입력을 빠르게 받기 위해 sys.stdin.readline 사용

# 상하좌우 이동을 나타내는 방향 벡터 (dx는 x축, dy는 y축 이동을 의미)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS(너비 우선 탐색) 함수 정의
def bfs(x, y):
    q = deque()  # 큐 생성
    q.append([x, y])  # 시작 지점을 큐에 삽입

    while q:
        x, y = q.popleft()  # 큐에서 현재 위치를 꺼냄

        # 상하좌우로 이동하면서 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 좌표가 유효한 범위 내에 있는지 확인
            if 0 <= nx < n and 0 <= ny < m:
                # 이미 방문했거나(visited[nx][ny]가 0이 아님), 이동할 수 없는 곳(1이 아님)이면 건너뜀
                if visited[nx][ny] or board[nx][ny] != 1:
                    continue

                # 방문하지 않았고 이동 가능한 곳이면, 현재 위치까지의 거리에서 1을 더해 기록
                visited[nx][ny] = visited[x][y] + 1
                q.append([nx, ny])  # 다음 탐색할 좌표를 큐에 추가

# n: 행, m: 열의 크기 입력
n, m = map(int, input().split())

board = []  # 지도 정보가 저장될 리스트
flag = 0  # 시작 지점(값이 2인 곳)을 찾으면 멈추기 위한 플래그
for i in range(n):
    temp = list(map(int, input().split()))  # 각 행을 입력받아 리스트로 변환
    board.append(temp)  # 변환한 리스트를 board에 추가

    if flag:  # 시작 지점이 이미 발견되었으면 더 이상 탐색하지 않음
        continue

    # 현재 행에서 시작 지점(2)을 찾는 과정
    for j in range(m):
        if temp[j] == 2:
            start_x, start_y = i, j  # 시작 지점 좌표 기록
            flag = 1  # 시작 지점을 찾았으므로 플래그를 세워 더 이상 찾지 않음

# 방문 여부 및 거리를 기록할 리스트 초기화
visited = [[0] * m for _ in range(n)]

# BFS를 이용해 시작 지점에서 다른 지점까지의 최단 거리를 계산
bfs(start_x, start_y)

# 최종적으로 탐색이 끝난 후, 도달할 수 없는 곳에 -1을 표시
for i in range(n):
    for j in range(m):
        if board[i][j] == 1 and not visited[i][j]:  # 갈 수 있는 곳(1)인데 방문하지 못했다면
            visited[i][j] = -1  # 도달할 수 없음을 표시

# 결과를 출력
for v in visited:
    print(*v)  # visited 리스트의 각 행을 공백으로 구분하여 출력

 

2. C++

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
using namespace std;

int board[1000][1000];  // 보드 상태를 저장할 배열

// BFS 함수 정의
void bfs(int x, int y, int n, int m) {
	int dx[] = { -1, 1, 0, 0 };  // 상하좌우 이동을 위한 배열
	int dy[] = { 0, 0, -1, 1 };  // 상하좌우 이동을 위한 배열
	vector<vector<int>> visited(n, vector<int>(m));  // 방문 여부를 저장할 2차원 배열
	queue<pair<int, int>> q;  // BFS를 위한 큐

	q.push(make_pair(x, y));  // 시작 지점 큐에 추가
	visited[x][y] = 1;  // 시작 지점 방문 처리
	board[x][y] = 0;  // 시작 지점은 0으로 설정 (시작 위치)

	// BFS 시작
	while (!q.empty()) {
		tie(x, y) = q.front();  // 큐에서 현재 위치를 꺼냄
		q.pop();

		// 상하좌우로 이동
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];  // 새로운 x 좌표
			int ny = y + dy[i];  // 새로운 y 좌표

			// 새로운 좌표가 보드 범위를 벗어나면 무시
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
				continue;

			// 아직 방문하지 않은 1인 영역에 대해 이동
			if (board[nx][ny] == 1 && !visited[nx][ny]) {
				q.push(make_pair(nx, ny));  // 큐에 추가
				visited[nx][ny] = 1;  // 방문 처리
				board[nx][ny] = board[x][y] + 1;  // 현재 위치에서의 거리 + 1
			}
		}
	}

	// BFS 종료 후, 방문하지 않은 1인 영역을 -1로 설정
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 1 && !visited[i][j]) {
				board[i][j] = -1;  // 도달할 수 없는 1인 영역은 -1로 표시
			}
		}
	}
}

int main() {
	int n, m;  // 보드 크기 n x m
	cin >> n >> m;

	int x, y;  // 시작 지점 좌표

	// 보드 상태 입력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 2) {  // 시작 지점이 2인 경우
				x = i;
				y = j;
			}
		}
	}

	bfs(x, y, n, m);  // BFS 실행

	// 결과 출력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << board[i][j] << " ";  // 최종 보드 상태 출력
		}
		cout << "\n";
	}

	return 0;
}

 

 

풀이 

 

1. BFS 사용:
   • 목표 지점(2)에서 출발하여 각 지점까지의 최단 거리를 구하기 위해 BFS를 사용한다.
2. 거리 배열 초기화:
   • 이동할 수 없는 지점은 -1로 표시하고, BFS 탐색 중에 방문한 지점의 거리를 업데이트한다.
   • 목표 지점에서 시작할 때 거리는 0으로 설정한다.
3. 지도 탐색:
   • 주어진 지도에서 목표 지점(2)을 찾은 후, 상하좌우로 이동하면서 최단 거리를 계산한다.
   • 벽(0)은 이동할 수 없으므로 그대로 유지하며, 도달할 수 없는 지점은 BFS 탐색 후에도 -1로 남긴다.
4. 결과 출력:
   • 각 지점의 거리를 출력하며, 벽은 그대로 0을 출력하고, 도달할 수 없는 지점은 -1로 출력한다.