BOJ_2665
😄 역시 골드 4는 골드 4인 이유가 있다.
2665번: 미로만들기
- 일단 필자의 경험상 2차원 맵을 움직이는 문제면
그래프이론
이다. - 검은 방을 흰 방으로 바꾸는 수를 최소한으로 만들어야 한다.
- 그렇다면 검은 방을 바꾼 수를 가지고 끝까지 가는게 좋을 것으로 판단된다.
- visit 배열을 놓은 뒤에 모든 수를 최대수로 설정해준다.
- 여기서 최대수는 모든 방이 검은 방이라고 했을 때 어림잡아 250개 정도로 초기화 시켜주면 된다.
초기화 작업
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
for (int j = 0; j < n; j++)
{
map[i][j] = s[j] - '0';
check[i][j] = 251;
}
}
미로를 뚫어보자
void bfs()
{
queue<pair<int, int> > q;
q.push(make_pair(0, 0));
check[0][0] = 0;
while (!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= n || nx >= n || ny < 0 || nx < 0)
continue;
if(map[ny][nx]==1)
{
if(check[ny][nx] > check[y][x])
{
q.push(make_pair(ny, nx));
check[ny][nx] = check[y][x];
}
}
else{
if(check[ny][nx] > check[y][x] + 1)
{
q.push(make_pair(ny, nx));
check[ny][nx] = check[y][x] + 1;
}
}
}
}
}
- 다른 bfs와 다른바가 없다.
- 다음 움직이려는 칸이 하얀칸이 경우 : check[y][x]가 더 작을 때만 움직인다.
- 다음 움직이려는 칸이 검은칸인 경우 :
check[y][x] + 1 < check[ny][nx]
일 때만 움직인다. 여기서 check는 검은 방을 거쳐온 수를 말한다.
전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>
using namespace std;
#define endl "\n"
int n;
int map[51][51];
int check[51][51];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void bfs()
{
queue<pair<int, int> > q;
q.push(make_pair(0, 0));
check[0][0] = 0;
while (!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= n || nx >= n || ny < 0 || nx < 0)
continue;
if(map[ny][nx]==1)
{
if(check[ny][nx] > check[y][x])
{
q.push(make_pair(ny, nx));
check[ny][nx] = check[y][x];
}
}
else{
if(check[ny][nx] > check[y][x] + 1)
{
q.push(make_pair(ny, nx));
check[ny][nx] = check[y][x] + 1;
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
for (int j = 0; j < n; j++)
{
map[i][j] = s[j] - '0';
check[i][j] = 251;
}
}
bfs();
cout << check[n - 1][n - 1] << endl;
}
Author And Source
이 문제에 관하여(BOJ_2665), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@luck2901/BOJ2665저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)