[Silver I] 미로 탐색 - 2178

문제 링크

성능 요약

메모리: 2196 KB, 시간: 0 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 격자 그래프

제출 일자

2025년 11월 6일 19:16:39

문제 설명

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

제출코드

// 백준 7576
//
// - 아이디어
// 또 BFS다. 최단경로를 찾는 문제로 DFS는 적합하지 않다.
// BFS 순회하면서 다음 칸으로 이동할때 카운트 +1씩 증가하며, 방문한곳은 패스하면서 진행
// 
// - 시간복잡도
// 배열크기 : 10^4
// bfs 순회: O(4*N*M) = O(n*m)= 10^4
// 
// - 자료구조
// 보드:  int[100][100]
// 큐: std::queue<std::pair<int,int>>

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

int N, M;
int board[100][100];
std::queue<std::pair<int, int>> que;

int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int BFS()
{
	int max = 0;
	while (!que.empty()) {
		auto point = que.front();
		que.pop();
		int ox = point.first;
		int oy = point.second;
		for (int i = 0; i < 4; i++) {
			int x = ox+ dx[i];
			int y = oy+ dy[i];
			if (x < 0 || x >= M || y < 0 || y >= N) {
				continue;
			}
			if (board[y][x] == 1) {
				board[y][x] = board[oy][ox] + 1;
				max = std::max(board[y][x], max);
				if (y == N - 1 && x == M - 1) {
					return max;
				}
				que.push(std::make_pair(x,y));
			}
		}
	}
	return 0;
}



int main()
{	
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	std::cin >> N >> M;
	std::string line;
	for (int y = 0; y < N; y++) {
		std::cin >> line;
		for (int x = 0; x < M; x++) {
			board[y][x] = static_cast<int>(line[x] - '0');
		}
	}

	que.push(std::pair<int,int>(0, 0));

	std::cout << BFS();

	

	return 0;
}

붙어서 주어진 값

붙어서 값이 주어졌다.

붙은 값을 입력받는 여러가지 방법

std::string line;
std::cin >> line;
for (int x = 0; x < M; x++) {
	board[y][x] = static_cast<int>(line[x] - '0');

본문처럼 string에 전달받고 아스키코드에 해당하는 int값으로 변경하기 위해 '0'을 빼기

   char line[M + 1];  
   for (int y = 0; y < N; y++) {  
       cin >> line;  
       for (int x = 0; x < M; x++)  
           board[y][x] = line[x] - '0';  
   }  

스트링 대신 c배열을 사용하면 더 빠를것이다

char val[100][100];
for...
	for ...
		std::cin >> val[y][x];
	

char배열에 직접 채움, 한줄씩 IO를 받는것보다 오버헤드가 클것으로 예상 - 비추천

char line[M + 1];  
for (int y = 0; y < N; y++) {  
	scanf_s("%s", line, sizeof(line));  
	for (int x = 0; x < M; x++)  
		board[y][x] = line[x] - '0';  
} 

cin보다 2배이상 빨랐다.

for...
	for ...
		int c = getchar();
		while (c == '\n' || c == '\r')
			c = getchar();
		board[y][x] = c - '0';
    }
}

c배열을 사용한 cin과 성능이 동일하다

size_t len = fread(buf, 1, sizeof(buf), stdin);  
char* p = buf;
for (int y = 0; y < N; y++) {  
    for (int x = 0; x < M; x++) {  
        while (*p == '\n' || *p == '\r') 
			p++;
        board[2][y][x] = *p - '0';
        p++;
    }  
}  

fread를 이용해서 한번에 버퍼를 읽어와 파싱하기, IO한번이라 빠를 수 밖에 없다.

결과적으로는 fread >> scanf > getchar == cin 순으로 성능차이가 났다.