DFS/BFS
- visited 백터를 사용하지 않고, 큐/스택에 방문할 요소를 삽입한 후에는 0으로 초기화 시켜주면 다시 방문할 수 없게 됨
- 인접노드(위/아래/왼/오)만 방문할 수 있는 경우,
이 배열을 통해 다음에 탐색할 노드 결정하기static int nextX[4]={1, 0, -1, 0}; static int nextY[4]={0, 1, 0, -1};
- 2차원 배열 탐색도 그래프라 생각하고 DFS, BFS 사용 가능 (x,y좌표를 pair로 저장해서 큐/스택에 저장)
문제점
int main (){
scanf("%d %d", &N, &M);
vector<vector<int>> arr(N);
char str[N][M];
//string으로 배열/그래프 입력받기
for(int i=0;i<N;i++){
scanf("%s", &str[i]);
}
//string을 int으 변환해서 int arr에 저장
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
arr[i].push_back(str[i][j]-'0');
}
}
BFS(arr);
printf("%d", arr[N-1][M-1]);
}문제1. 띄어쓰기 없이 입력되는 값
처음에 cin>>{int변수} 로 받았더니 입력조차 되지 않음
1 해결책
string으로 받아서, int로 바꾼 후, 새로운 int배열에 (for문 안에서) 하나씩 넣어줌
문제2. string에서 int로 변환
string[{행의 개수}]배열을 이용하여 한줄씩 입력받음 -> 입력이 다 끝난 후에, str[i][j]-'0'
이렇게 int형 배열에 하나씩 넣어주었더니 중간에 아예 종료되어버림
-> 아마 string 타입 - char형 이어서 그런듯
2 해결책
char str[N][M]char형 2차원 배열 선언- 한 칸에 하나의 문자만 저장
str[i][j]-'0'를 통해 char를 int로 변환해서 arr[i].push_back() 해줌
문제3. arr[i].push_back() 먹통
처음에는 2의 문제 때문에 계속 종료되는 줄 알았으나, 한줄한줄 print("{아무말}") 을 해보니 벡터 push_back이 안되는 거였다. -> push_back() 에러 검색
vector에서 push_back()과 인덱스[i] 사용시 주의할 점
arr[i].push_back(str[i][j]-'0');내 코드처럼 인덱스(배열처럼 직접 접근)와 push_back()을 모두 사용할 때 문제점- push_back() : vector를 정의하고 난 후 메모리를 따로 잡지 않아도 item을 추가할 수 있다.
- 인덱스로 직접 접근 : item의 개수를 선언해서 메모리(벡터의 사이즈)를 미리 정해줘야 한다. 안그러면 에러 발생
3 해결책
벡터 선언할 때 행의 개수(사이즈)를 정해주었더니 해결됨
vector<vector<int>> arr(N);
vector<int> vec;
vec[0] = 3; //(X) <-- vec 객체의 메모리를 할당하지 않았기 때문에 실행 에러남.
vec.push_back(3); //(O)
//-------------------------------------------------//
vector<int> vec(4); <-- vec 객체에 4개의 item에 대한 메모리를 정해줌.
vec[0] = 3; //(O) <--- 인덱스 접근은 OK.
vec.push_back(2); //(O)
Q1
문제2 해결하는 과정에서 생긴 의문
Q1. 근데 아래의 코드처럼 string을 char형으로 전환해도 왜 오류가 나는 걸까..
string str[N][M];
for(int i=0;i<N;i++){
scanf("%s", &str[i]);
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
char tmp = str[i][j]; //string을 char형으로 전환
arr[i].push_back(tmp-'0');
}
}Q2
문제3 해결하는 과정에서 생긴 의문
처음 코드를 짰을 때에는 N, M을 static 변수로 선언 -> arr벡터 선언 -> input을 받고 -> arr벡터 resize
- Q2. resize가 있으니까 그 뒤의 아무것도 실행되지 않음,,
: resize중에 오류가 난건데,, -> 왜일까?
for(int i=0;i<N;i++){
arr[i].resize(M, 0);
}최종코드
/**
*** BFS(큐) 이용하여 최단경로 구하기
* visited 배열 필요 없이, 방문할 노드는 큐에 넣어준 후에
arr[i][j]={그래프의 depth}으로 바꿔주기
-> (0,0)일 때에만 탐색 후에도 depth가 1일 테니 거기만 제외하는 if조건문 작성
*/
#include <cstdio>
//#include <string>
#include <algorithm>
#include <vector>
#include <queue>
//#include <utility> : pair사용시 필요, but queue의 속성으로 쓰일 땐 필요없음
using namespace std;
static queue<pair<int, int>> q;
static int nextX[4]={1, 0, -1, 0};
static int nextY[4]={0, 1, 0, -1};
static int N, M, cnt=2;
void BFS(vector<vector<int>>& arr){
q.push(make_pair(0, 0));
while(!q.empty()){
int nowX=q.front().first;
int nowY=q.front().second;
q.pop();
for(int i=0;i<4;i++){
int x = nowX+nextX[i];
int y = nowY+nextY[i];
if(x>=0 && y>=0 && x<N && y<M){ //좌표 유효성 검사
if(!(x==0&&y==0) && arr[x][y]==1){ //방문 노드 검사
arr[x][y]=arr[nowX][nowY]+1; //깊이 업데이트
q.push(make_pair(x, y));
}
}
}
}
}
int main (){
scanf("%d %d", &N, &M);
vector<vector<int>> arr(N);
char str[N][M];
for(int i=0;i<N;i++){
scanf("%s", &str[i]);
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
arr[i].push_back(str[i][j]-'0');
}
}
BFS(arr);
printf("%d", arr[N-1][M-1]);
}