[알고리즘] 2178번: 미로 탐색 (+ 붙어있는 입력)

 

0. 문제

 

2178번: 미로 탐색

 

---

1. 문제 이해

 

1. 동일한 가중치를 가진 경우에 최단거리 구하기 → BFS
2. N, M(2 ≤ N, M ≤ 100)를 입력받는다. → 최대 100 * 100의 2차원 배열을 선언한다.
3. 각각의 수들은 붙어서 입력으로 주어진다. → ???

// 예제 입력
4 6
101111
101010
101011
111011

 

---

2. 붙어있는 입력을 분리하는 방법

 

44
1000
0000
0111
0000

 

---

가. string으로 변환

 

첫 번째는 string으로 받아 변환하는 방법.

#include<bits/stdc++.h>
using namespace std;
int n, m, a[10][10];
string s;

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0; j < m; j++){
            a[i][j] = s[j] - '0';
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
          cout << a[i][j];
        }
      cout << '\n';
    }
}

/*
44
1000
0000
0111
0000
1000
0000
0111
0000
*/

cin으로 받을 때는 개행문자(띄어쓰기, 한 줄 띄기)까지 받을 수 있다. 주의할 것.

 

---

나. scanf로 받기

#include <bits/stdc++.h>
using namespace std; 
int a[10][10], n, m;
//char a[10][10]; //char형
int main(){
    cin>>n>>m; 
    for(inti=0;i<n;i++){
        for(intj=0;j<m;j++){
            scanf("%1d", &a[i][j]); //int형
            //scanf("%c", &a[i][j]); //char형
    }
    }
    return 0; 
}

 

특수문자, 개행문자(띄어쓰기, 한줄띄기)까지 받을 수 있다. 주의할 것.

 

---

다. 입력의 끝을 모를 때

 

while(scanf("%d",&n) != EOF)
while(cin >> n) 

 

---

2. 제출

// 2178번 미로 탐색
#include <iostream>
#include <queue>
#include <utility> // for pair
#include <tuple> // for tie
using namespace std;

const int max_nm = 104;

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int n, m, a[max_nm][max_nm], visited[max_nm][max_nm], y, x, sy, sx, ey, ex;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	sy = 0; sx = 0;
	ey = n-1; ex = m-1;

	//맵 입력
	for(int i=0; i<n; i++){
		string s;
		cin >> s;
		for(int j=0; j<m; j++){
			a[i][j] = s[j] - '0';
		}
	}

	queue<pair<int, int>> q;

	visited[0][0] = 1;
	q.push({0,0});
	while(q.size()){
		tie(y, x) = q.front(); q.pop();
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			bool underflow = ny < 0 || nx < 0;
			bool overflow = ny >= n || nx >= m;
			if(underflow || overflow) continue;
			bool noAccess  = a[ny][nx] == 0;
			if(noAccess || visited[ny][nx]) continue;
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ny, nx});
		}
	}
	cout << visited[ey][ex] << "\n";
	
	return 0;
}

• bool underflow = ny < 0 || nx < 0; bool overflow = ny >= n || nx >= m;
  : 언더, 오버플로우 확인 후 실행할 것!

 

---