미로 탈출

출처::https://www.acmicpc.net/problem/2178

 

1. 문제 이해 및 해결과정

-BFS

 

2. 풀이방법

1. pair<int,int> 와 queue이용해서 푸는 것 -visited배열로 값을 바꾸면서 푸는 방법

#if 0
//미로탐색
//https://www.acmicpc.net/problem/2178

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

int N, M;//세로, 가로
int map[100 + 10][100 + 10];
int visited[100 + 10][100 + 10];
int dh[] = { -1,1,0,0 }; //상하좌우
int dw[] = { 0,0,-1,1 };

int BFS() {
	//1.초기화
	
	queue <pair<int,int>> q;

	//2.시작점 저장
	q.push({ 1, 1 });
	visited[1][1] = 1;

	//3. 반복문
	while (!q.empty()) {
		pair<int, int> cur;
		cur = q.front();
		q.pop();

		
		for (int i = 0; i < 4; i++) {
			int nh = cur.first + dh[i];
			int nw = cur.second + dw[i];

			if (nh <= 0 || nh > N || nw <= 0 || nw > M)continue;
			if (map[nh][nw] == 0 || visited[nh][nw] >= 1)continue;
			visited[nh][nw] = visited[cur.first][cur.second]+1; //cur.t + 1 역할
			q.push({ nh,nw });
		//	cout << nh << " " << nw << " " << endl;
		}
	
	}

	//4. 결과
	return visited[N][M];

}
void InputData() {
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
}
int main() {
	int sol;
	
	freopen("input.txt", "r", stdin);

	InputData();

	sol = BFS();
	cout << sol;
	return 0;
}

#endif

2. 구조체와 queue 이용해서 푸는것  -cur.t로

#if 01
//미로탐색- 구조체 + queue 쓸때
//https://www.acmicpc.net/problem/2178

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

int N, M;//세로, 가로
int map[100 + 10][100 + 10];
int visited[100 + 10][100 + 10];
int dh[] = { -1,1,0,0 }; //상하좌우
int dw[] = { 0,0,-1,1 };

typedef struct{
	int h;
	int w;
	int t;
}info;

int BFS() {
	//1.초기화

	queue <info> q;
	info cur;

	//2.시작점 저장
	q.push({ 1, 1 ,1});
	visited[1][1] = 1;

	//3. 반복문
	while (!q.empty()) {

		cur = q.front();
		q.pop();

		//아래 문장이 없으면 답이 달라짐 = 최소의 칸 수가 나오지 않음
		if (cur.h == N && cur.w == M)return cur.t;

		for (int i = 0; i < 4; i++) {
			int nh = cur.h + dh[i];
			int nw = cur.w + dw[i];

			if (nh <= 0 || nh > N || nw <= 0 || nw > M)continue;
			if (map[nh][nw] == 0 || visited[nh][nw]==1)continue;
			visited[nh][nw] = 1;
			q.push({ nh,nw,cur.t+1 });
			//cout << nh << " " << nw << " " <<cur.t+1<< endl;
		}

	}

	//4. 결과
//	return cur.t;

}
void InputData() {
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
}
int main() {
	int sol;

	freopen("input.txt", "r", stdin);

	InputData();

	sol = BFS();
	cout << sol;
	return 0;
}

#endif

3) python

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
board = []

for _ in range(n):
    board.append(list(map(int, input().rstrip()))) # readline의 경우 맨 뒤에 '\n'까지 입력받으므로 제거해줘야 함

dh=[-1,0,1,0] #시계방향
dw=[0,1,0,-1]

Q=deque()
Q.append((0,0))

def bfs(x,y):

    while Q: 
        h, w = Q.popleft()
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]

            if 0<=nh<n and 0<=nw<m and board[nh][nw]==1:
                board[nh][nw] = board[h][w]+1
                Q.append((nh,nw))
        
    return board[-1][-1]

print(bfs(0,0))

 

 

3. 오답원인

 

4. 알게된 점

1. pair<int,int> 와 queue이용해서 푸는 것 -visited배열로 값을 바꾸면서 푸는 방법

2. 구조체와 queue 이용해서 푸는것  -cur.t로