[풀이, BFS default]백준 풀이(VII/16932, 2667)
문제풀이
미로탐색 (2178, 이차원 배열 BFS-1)
- N*M 크기의 배열로 표현되는 미로
- (0,0) to (N,M)으로 이동하는 최소 칸 수(시작점, 마지막점도 포함)
- 2<= N,M <=100
- (짜증) 숫자가 붙어서 입력된다.
-> scanf %1d로 해결!
회고
특이한 입력, 기본적인 BFS, 초기화오류, 오타 등 나올 수 있는 기본적인건 다 나온 것 같다.
자꾸틀려서 왜그런가 했더니 초기화오류라는 답변이 있어서 init()함수를 생성해서 정답을 맞췄다.
2차원 배열 BFS의 정석을 보여주는 문제였고 이 코드를 많이 참조할 것 같다. 이상
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
int n, m;
bool map[101][101];
int check[101][101];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void init(){
for(int i=0; i<101; i++){
for(int j=0; j<101; j++){
map[i][j]=false;
check[i][j]=0;
}
}
}
bool isInside(int x, int y){
if(x>=0 && x<n && y>=0 && y<m) return true;
else return false;
}
void bfs(int sx, int sy){
queue<pair<int,int>> q;
q.push(make_pair(sx,sy));
check[sx][sy] = 1;
while(!q.empty()){
pair<int, int> x = q.front();
q.pop();
//동서남북
for(int i=0; i<4; i++){
pair<int,int>y;
y = make_pair(x.first+dx[i], x.second+dy[i]);
int nx = y.first;
int ny = y.second;
if(isInside(nx, ny) && check[nx][ny]==0 && map[nx][ny]){
check[nx][ny] = check[x.first][x.second]+1;
q.push(y);
}
}
}
}
int main(void) {
cin >> n >> m;
init();
//입력
for(int i1=0; i<n; i++){
for(int j=0; j<m; j++){
int temp;
scanf("%1d", &temp);
if(temp==1) map[i][j] = true;
}
}
bfs(0,0);
cout << check[n-1][m-1];
return 0;
}
모양만들기 (16932,이차원 배열 BFS-3)
- 단지번호붙이기의 응용!
N*M boolean배열에서 모양을 찾으려고 한다.모양이란 연결되어 있는 1의 최대 개수 (그래프로 모델링 가능)- 이 문제는 조금 어렵다. (한 칸을 변경할 수 있기 때문에!)
[불가능]풀이1. 모든 0을 1로 변경하여 DFS/BFS를 모두 연산하는 방법 (시간이 오래 걸린다)
바꿀 수 있는 경우의 수 (NM) * O(NM) = O(N^2 M^2) - 불가능한 경우의 수
즉,
- 완전 방법이 잘못되었거나
- 불필요한 케이스를 줄여야한다.
위 경우는 2. 불필요한 케이스를 줄여야한다.에 해당
풀이2. BFS, DFS를 한 번 실행해서 모든 칸을 그룹짓고, 그룹의 크기를 미리 구해놓는다.
다음 모든 0을 1로 바꾸는 경우를 고려하여 BFS 없이 계산할 수 있다. (바꾸는 0을 기준으로 상하좌우를 조사하여 그룹이 연결되어있다면 값을 합친다.)
- c++의 unique를 사용했는데 뭐하는 놈인지 알아볼 것
풀이
풀이 방식을 생각해보았다.
- 처음 등장한1에서 BFS()
- 경로값(map) INF로 모두 변경
- check[][]배열의 max값 group[m]에 입력
- 전체 search
… m회 반복
- 처음 등장한1에서 BFS()
- 경로값(map) INF로 모두 변경
- check[][]배열의 max값 group[m]에 입력
- 전체 search
반복해서 Search했을 때 1이 없다면 그룹화 완료.
후 모든 0에 대해 1로 바꾸는 작업진행
- 0 선택 후 상,하,좌,우 확인 해서 그룹이 있다면 값을 확인한 뒤 group[m]의 개수를 합쳐준다.
- 다시 0으로 바꾼 뒤 zvisit[][]배열에 표시하고 반복
회고
처음부터 끝까지 싹다푼건 이게 거의 처음인 것 같다. 문제 풀이방식을 수업에서 들어서 겨우 풀어냄… 그래도 엄청 뿌듯하다.
코드가 꽤 지저분한데 (중간에 1씩 idx가 차이나거나 예외처리하는 것들..) 이 코드를 다시 보기도 힘드니 잘 정리해서 써먹야야겠다.
#include <iostream>
#include <math.h>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
int n,m, groupCount,maxGroupSize=0;
int map[1000][1000], check[1000][1000];
//사이즈 늘어날 수 있음
int group[10000];
vector<int> groupV;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void init(){
for(int i=0; i<26; i++){
group[i]=0;
for(int j=0; j<26; j++){
map[i][j]=false;
check[i][j]=0;
}
}
}
bool isInside(int x, int y){
if(x>=0 && x<n && y>=0 && y<m) return true;
else return false;
}
bool findDuplGroup(int idx){
int temp = groupV.size();
for(int i=0; i<temp; i++){
//이미 확인했던 그룹이면
if(groupV[i]==idx) return false;
}
return true;
}
void pickZero(int sx, int sy){
int temp=0;
for(int i=0; i<4; i++){
int nx = sx + dx[i];
int ny = sy + dy[i];
//8.격자안에 위치하고 그룹에 속한경우
if(isInside(nx,ny) && map[nx][ny]>1){
//상 하 좌 우에 이미 합친 Group이 없는 경우....
if(findDuplGroup(INF-map[nx][ny])){
groupV.push_back(INF-map[nx][ny]);
//group[INF-map[nx][ny]] = 인접한 그룹의 사이즈 + 1, groupcount가 1이 적게 들어가있어서그렇다
temp += group[INF-map[nx][ny]]+1;
}
}
maxGroupSize = max(maxGroupSize, temp);
}
groupV.clear();
}
void bfs(int sx, int sy){
queue<pair<int,int>> q;
q.push(make_pair(sx,sy));
check[sx][sy] = 1;
map[sx][sy] = INF-groupCount;
while(!q.empty()){
pair<int, int> x = q.front();
q.pop();
//동서남북
for(int i=0; i<4; i++){
pair<int,int>y;
y = make_pair(x.first+dx[i], x.second+dy[i]);
int nx = y.first;
int ny = y.second;
//2.격자안에 있고, 아직 방문한적이 없으며, 집이 있는 경우
if(isInside(nx, ny) && check[nx][ny]==0 && map[nx][ny]>0)
{
//3.몇 번째로 방문했는지 표시하고
check[nx][ny] = check[sx][sy]+1;
//4.큐에 넣어 다음 search 준비를 하고
q.push(y);
//6.map값도 변경
map[nx][ny] = INF-groupCount;
//5.group화를 위해 groupCount를 세준다.
group[groupCount]++;
}
}
}
}
void printMap(){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cout << map[i][j] << " ";
}
cout << endl;
}
}
int main(void) {
cin >> n >> m;
init();
//입력
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
int temp;
scanf("%1d", &temp);
if(temp==1) map[i][j] = true;
}
}
groupCount=0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(map[i][j]==1)
{
//1. 처음 등장한 1에서 BFS()
bfs(i,j);
groupCount++;
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(map[i][j]==0)
{
//7. 0인 녀석들을 골라 1로 변경
pickZero(i,j);
}
}
}
//+1인 이유는 위에서 자기자신(0->1)을 계산하지 않았기 때문이다.
cout << maxGroupSize+1;
}
단지번호붙이기 (2667,이차원 배열 BFS-2)
- 정사각형모양의 지도가 있다. (1= 집이 있는 곳, 0 = 집이 없는 곳)
- 단지(연결된 집들의 모임)를 정의하고 단지에 번호를 붙이려 한다.
풀이가 잘 이해가 안되는 이유? : 모델링을 안해서
그래프로 모델링을 해보자
needs1. 탐색을 하며 지나온 길을 등록하는 2차원 배열 needs2. bfs 구현을 위한 queue
회고
EZEZ….
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
#define INF 987654321
using namespace std;
vector<int> gc;
int n, groupCount=0;
int group[1000];
int map[26][26];
int check[26][26];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void init() {
for (int i = 0; i < 26; i++) {
group[i] = 0;
for (int j = 0; j < 26; j++) {
map[i][j] = 0;
check[i][j] = 0;
}
}
}
bool isInside(int x, int y) {
if (x >= 0 && x < n && y >= 0 && y < n) return true;
else return false;
}
void bfs(int sx, int sy) {
queue<pair<int, int>> q;
q.push(make_pair(sx, sy));
check[sx][sy] = 1;
while (!q.empty()) {
pair<int, int> x = q.front();
q.pop();
//동서남북
for (int i = 0; i < 4; i++) {
pair<int, int>y;
y = make_pair(x.first + dx[i], x.second + dy[i]);
int nx = y.first;
int ny = y.second;
if (isInside(nx, ny) && check[nx][ny] == 0 && map[nx][ny]>0) {
check[nx][ny] = check[x.first][x.second] + 1;
q.push(y);
map[nx][ny] = INF - groupCount;
group[groupCount]++;
}
}
}
groupCount++;
}
int main(void) {
cin >> n;
init();
//입력
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int temp;
scanf("%1d", &temp);
if (temp == 1) map[i][j] = true;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(map[i][j]==1) bfs(i, j);
}
}
cout << groupCount << endl;
for (int i = 0; i < groupCount; i++) {
gc.push_back(group[i]);
}
sort(gc.begin(), gc.end());
for (int i = 0; i < gc.size(); i++) {
cout << gc[i]+1 << endl;
}
return 0;
}
숨바꼭질(1697, 기본BFS)
- 나3곱2를 풀기 위한 기본 문제
- 수빈(N), 동생(K)
- 수빈 = 이동 OR 순간이동
- X걷기 = X+1 OR X-1
- 순간이동 = 2*X
- 수빈이가 동생을 찾을 수 있는 가장 빠른 시간은?
거꾸로 계산해보자.
짝수면 무조건 나누기가 빠르다.
- 시간 줄일 거 없이 전부 다 봤다.
- 10분만에 풀었네…. 행복하다
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
#define INF 987654321
using namespace std;
int n, k;
int map[100001];
int check[100001];
void init() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
map[i] = 0;
check[i] = 0;
}
}
}
bool isInside(int x) {
if (x >= 0 && x <= 100000) return true;
else return false;
}
void bfs(int s) {
queue<int> q;
q.push(s);
check[s]= 1;
while (!q.empty()) {
int x = q.front();
q.pop();
//동서남북
for (int i = 0; i < 3; i++) {
int y;
if (i == 0) y = 2 * x;
else if (i == 1) y = x + 1;
else y = x - 1;
if (isInside(y) && check[y] == 0) {
check[y] = check[x] + 1;
q.push(y);
}
//성공조건
if (y == k) {
break;
}
}
}
}
int main(void) {
cin >> n >> k;
init();
bfs(n);
//for (int i = 0; i < 20; i++) {
// cout << "check[" << i << "]= " << check[i] << endl;
//}
cout << check[k] - 1 << endl;
return 0;
}
댓글남기기