[풀이]백준 풀이(II/16924, 16928, 16948, 16954)

이거 사용가능?

문제풀이

십자가 찾기(16924, 브루트포스)

중요한 조건

사용하는 십자가의 수 <=N,M <= 100 큰 십자가는 작은 십자가를 포함한다. 모든 별이 중심이라고 생각하고 가장 큰 십자가를 찾으면 된다! O(NM*(N+M)) = O(N^3)

---

회고

우선 패스,,

[필수]뱀과 사다리게임(16928, BFS)

• 사실상 아래의 BFS랑 같은 소스이므로 구현해보자.

  void bfs(int 시작){
    queue<int> q;
    q.push(시작); check[시작] = true; dist[시작] = 0;
    while(!q.empty()){
        int x = q.front(); q.pop();
        for(가능한 모든 다음 정점 y){
            if(check[y] == false) {
                q.push(y); check[y] = true; dist[y]=dist[x]+1;
            }
        }
    }
  }
  

• 1 TO 100 이동하는 게임
• 사다리 = +, 뱀 = -
• 주사위 값을 정할 수 있을 때 100까지 갈 수 있는 최단거리(최소)
• 칸 = vertex, 칸 TO 칸 = edge
• 구하는 것 = 주사위를 굴리는 최소 횟수 (가중치=1)

최소: 최소라는 키워드가 나오면 BFS를 일단 생각해본다.

• X의 다음 경우의 수 (X+ 1~6, 사다리, 뱀)
• 새로운 배열 next[x]를 만들어서, x에 도착한 이후에 가야할 곳을 모두 기록

풀기 전 BFS에 대해 더 공부하기 위해 코드플러스 강의를 듣고 여기에 정리해 두었다.

회고

짜고보니 답이 이상해서 한참 고생했다.. //요기 부분이 누락되어서 그랬던 것. 처음에는 check배열까지 만들었다가 강의를 듣고나서 고쳤다. 아직 자꾸 재귀처럼 생각하게되는데 종이에 써가면서 안풀면 조금 어렵다..

#include <iostream>
#include <queue>

using namespace std;
int dist[101];
int next_num[101];
void bfs(int start){
	queue<int> q;
	q.push(start);
	dist[start]=0;
	while(!q.empty()){
		int x= q.front();
		q.pop();
		for(int i=1; i<=6; i++){
			int y= x+i;
			if(y>100) continue;
			//요기.
			y= next_num[y];
			if(dist[y] == -1){
				dist[y]= dist[x]+1;
				q.push(y);
			}
		}
	}
}
int main(){
	int n, m, x, y, u, v;
	 for (int i=1; i<=100; i++) {
	//dist[i] == -1인 경우 check되지 않음을 뜻함
		 next_num[i] = i;
	        dist[i] = -1;
	}
	cin >> n >> m;
	for(int i=0; i<n; i++){
		cin >> x >> y;
		next_num[x]=y;
	}
	for(int i=0; i<m; i++){
		cin >> u >> v;
		next_num[u]=v;
	}
	bfs(1);
	cout << dist[100];
}

데스나이트(16948, BFS)

• 이동할 경우 이동횟수가 1개 늘어난다 = 가중치가 1이다. (BFS)
• d[x]={-2,-2,0,0,2,2}
• d[y]={-1,+1,-2,+2,-1,+1}

모델링을 직접 해보자

회고

실수1. dist배열의 초기화 실수 (-1로 꽉안채웠다.. memset을 사용하자)

실수2. dx, dy루프의 k값을 4로했다 ㅎ;;

실수3. bfs안에서 dist 값을 변경하는 조건문이 부족하거나 오타가 있었다.

어쩃든 clear!

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
//여기서 초기화가 안되었네.
//int dist[201][201] = {-1,};
int dist[201][201];
int n, rs, cs, re, ce;

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

void bfs(int rs, int cs){
	queue<pair <int, int>> q;
	q.push(make_pair(rs,cs));
	dist[rs][cs] = 0;
	while(!q.empty()){
		pair<int, int> x = q.front();
		q.pop();
		//k=4로 했었다..
		for(int k=0; k<6; k++){
			pair<int, int> y = make_pair(x.first + dx[k], x.second +dy[k]);
			//조건문이 조금 부족했다.
			//if(y.first == re && y.second == ce) continue;
			if(0<= y.first)
			{
				if(y.first < n)
				{
					//오타가 있었다.
					if(0 <= y.second)
					{
						if(y.second <n)
						{
							if(dist[y.first][y.second]==-1)
							{
								q.push(y);
								dist[y.first][y.second] = dist[x.first][x.second] +1;
							}
						}
					}
				}
			}
		}
	}
}

int main(){

	cin >> n;
	cin >> rs >> cs >> re >> ce;

    memset(dist,-1,sizeof(dist));
	bfs(rs,cs);

	cout << dist[re][ce];


}