백준 2178

1. 문제 이해

 

출처:https://blog.encrypted.gg/941

 

이 문제는 BFS를 응용해서 풀 수 있다.

시작지점부터 인접한 곳으로 이동할 때마다 거리를 1씩 증가시키면 된다. 

출처:https://blog.encrypted.gg/941

 

연결된 칸들을 모두 방문한 경우 각 끝지점에서 시작지점을 빼면 시작지점으로 부터 몇 칸 이동했는지 알 수 있다.

이걸 이용해서 (1,1) ~ (N,M) 까지의 거리를 구할 수 있다.

 

2. 코드

#include <iostream>
#include <utility>
#include <queue>
using namespace std;
#define X first
#define Y second 

// 상하좌우 네 방향을 고정
// (1,0) : 우, (0,1) : 상, (-1,0) : 좌, (0,-1) : 하
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

// 배열의 크기를 문제와 딱 맞게 잡아도 상관없는데 
// 내가 필요한 배열의 크기를 아주 살짝 잘못 생각했더라도 맞을 수 있게 하기 위해서 여유를 줌
// 불필요한 메모리를 사용하지 않는다는 관점에서 크기를 딱 맞게 잡는게 베스트지만 몇 칸 여유를 준다고 해서 큰 문제가 생기지 않음
string board[102];
int dist[102][102];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> board[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dist[i][j] = 0;
        }
    }

    // 시작지점 (0,0)
    queue<pair<int, int>> Q;
    dist[0][0] = 1;
    Q.push({ 0, 0 });

    while (!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(dist[nx][ny] >= 1 || board[nx][ny] == '0') continue;
            dist[nx][ny] = dist[cur.X][cur.Y] + 1; // 거리증가
            Q.push({ nx, ny });
        }
    }
    
    cout << dist[n - 1][m - 1];

    return 0;
}

 

 

복습

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

string board[102];
int vis[102][102];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int n, m;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	// 1.입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}

	// 2.로직
	// (1,1) 출발 ~ (n,m) 도착한다고 가정	
	queue<pair<int, int>> Q;
	vis[0][0] = 1;
	Q.push({ 0,0 });

	while (!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];

			// 범위 체크 
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			// 방문 여부, 1인지 체크
			if (vis[nx][ny] >= 1 || board[nx][ny] != '1') continue;

			vis[nx][ny] = vis[cur.first][cur.second] + 1;			
			Q.push({ nx,ny });
		}
	}

	cout << vis[n-1][m-1];
		
	return 0;
}