값이 총 3개일 때, 트리 모양으로 가정합니다. D(1), D(2), D(3), D(4)가 있습니다. D() 안의 숫자는 level을 뜻합니다. D(1)은 0 0 0이고, D(2)는 첫째 값, D(3)는 둘째 값, D(4)는 셋째 값입니다. 루트부터 전위 순회를 하면서 왼쪽은 ch[level] = 1; 오른쪽은 ch[level] = 0; 입니다. level 1은 0 0 0입니다. level이 4일 때 부분집합을 출력합니다.
#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>
#define MAX_SIZE 101
using namespace std;
// 위, 오른, 아래, 왼
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n, m; // 행과 열의 수
int dis[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE]; // 지도
bool visited[MAX_SIZE][MAX_SIZE]; // 방문했는지를 표시하는 지도
// BFS
void bfs(int x, int y){
queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.
// 처음 x,y를 방문 했기때문에
visited[x][y] = true;
while(!q.empty()){
// 큐의 현재 원소를 꺼내기
x = q.front().first;
y = q.front().second;
q.pop();
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < m){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;
// 해당 단지의 집의 수를 증가시킴
dis[nx][ny] = dis[x][y] + 1;
// 큐에 현재 nx,ny를 추가
q.push(make_pair(nx,ny));
}
}
}
}
}
int main (){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++)
//입력을 1개씩 숫자로 끊어서 받습니다 -> %1d
scanf("%1d", &map[i][j]);
}
dis[0][0] = 1;
bfs(0, 0);
printf("%d\n",dis[n-1][m-1]);
}
#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>
#define MAX_SIZE 25
using namespace std;
// 위, 오른, 아래, 왼
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n; // 행과 열의 수
int group_id; // 단지의 번호로 첫번째 단지부터 1로 시작
int groups[MAX_SIZE * MAX_SIZE]; // 각 단지별 집의 수
int map[MAX_SIZE][MAX_SIZE]; // 지도
bool visited[MAX_SIZE][MAX_SIZE]; // 방문했는지를 표시하는 지도
// BFS
void bfs(int x, int y){
queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.
// 처음 x,y를 방문 했기때문에
visited[x][y] = true;
groups[group_id]++;
while(!q.empty()){
// 큐의 현재 원소를 꺼내기
x = q.front().first;
y = q.front().second;
q.pop();
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;
// 해당 단지의 집의 수를 증가시킴
groups[group_id]++;
// 큐에 현재 nx,ny를 추가
q.push(make_pair(nx,ny));
}
}
}
}
}
int main (){
scanf("%d", &n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
//입력을 1개씩 숫자로 끊어서 받습니다 -> %1d
scanf("%1d", &map[i][j]);
}
// 전체 지도 탐색
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// 집이면서 방문하지 않았다면 -> 방문
if(map[i][j]==1 && visited[i][j]==false){
// 해당 지역에 단지 id를 부여하고
group_id++;
// 탐색
bfs(i, j);
}
}
}
// 단지마다 집들의 수로 오름차순 정렬
// ID는 1부터 시작
// 함수 사용법: https://twpower.github.io/71-use-sort-and-stable_sort-in-cpp
sort(groups + 1, groups + group_id + 1);
printf("%d\n", group_id);
for (int i = 1; i <= group_id; i++) {
printf("%d\n", groups[i]);
}
}
#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>
#define MAX_SIZE 100001
using namespace std;
int n, m; // 수빈, 동생 위치
int dis[MAX_SIZE];
bool visited[MAX_SIZE]; // 방문했는지를 표시하는 배열
// BFS
void bfs(int x){
queue <int> q; // 이용할 큐
q.push(x);
int nx;
// 처음 x를 방문 했기때문에
visited[x] = true;
while(!q.empty()){
// 큐의 현재 원소를 꺼내기
x = q.front();
q.pop();
// 해당 위치의 주변을 확인
nx = x * 2;
// 지도를 벗어나지 않고, 방문한 적 없으면
if(nx <= MAX_SIZE-1 && visited[nx] == false){
visited[nx]=true;
// 해당 단지의 집의 수를 증가시킴
dis[nx] = dis[x] + 1;
if(nx == m){
printf("%d\n", dis[nx]);
return;
}
// 큐에 현재 nx를 추가
q.push(nx);
}
// 해당 위치의 주변을 확인
nx = x + 1;
// 지도를 벗어나지 않고, 방문한 적 없으면
if(nx <= MAX_SIZE-1 && visited[nx] == false){
visited[nx]=true;
// 해당 단지의 집의 수를 증가시킴
dis[nx] = dis[x] + 1;
if(nx == m){
printf("%d\n", dis[nx]);
return;
}
// 큐에 현재 nx를 추가
q.push(nx);
}
// 해당 위치의 주변을 확인
nx = x - 1;
// 지도를 벗어나지 않고, 방문한 적 없으면
if(0 <= nx && visited[nx] == false){
visited[nx]=true;
// 해당 단지의 집의 수를 증가시킴
dis[nx] = dis[x] + 1;
if(nx == m){
printf("%d\n", dis[nx]);
return;
}
// 큐에 현재 nx를 추가
q.push(nx);
}
}
}
int main (){
scanf("%d%d", &n, &m);
if(n == m){
printf("0\n");
} else {
dis[n] = 0;
bfs(n);
}
}
- 지도 유형은 아니지만, 지도 레퍼런스를 가지고 풀었다.
- 2차원 배열을 모두 1차원으로 변경
- 세세한 예외 조건들을 설정하는게 까다로운 문제
응용문제) 백준 5014 스타트링크
#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>
#define MAX_SIZE 10000001
using namespace std;
int f, s, g, u, d;
int dis[MAX_SIZE];
bool visited[MAX_SIZE]; // 방문했는지를 표시하는 배열
// BFS
void bfs(int x, int up, int down){
queue <int> q; // 이용할 큐
q.push(x);
int nx;
// 처음 x를 방문 했기때문에
visited[x] = true;
while(!q.empty()){
// 큐의 현재 원소를 꺼내기
x = q.front();
q.pop();
// 해당 위치의 주변을 확인
nx = x + up;
// 지도를 벗어나지 않고, 방문한 적 없으면
if(nx >= 1 && nx <= f && visited[nx] == false){
visited[nx]=true;
// 해당 단지의 집의 수를 증가시킴
dis[nx] = dis[x] + 1;
if(nx == g){
printf("%d\n", dis[nx]);
return;
}
// 큐에 현재 nx를 추가
q.push(nx);
}
// 해당 위치의 주변을 확인
nx = x - down;
// 지도를 벗어나지 않고, 방문한 적 없으면
if(nx >= 1 && nx <= f && visited[nx] == false){
visited[nx]=true;
// 해당 단지의 집의 수를 증가시킴
dis[nx] = dis[x] + 1;
if(nx == g){
printf("%d\n", dis[nx]);
return;
}
// 큐에 현재 nx를 추가
q.push(nx);
}
}
printf("use the stairs\n");
}
int main (){
scanf("%d%d%d%d%d", &f, &s, &g, &u, &d);
if(s == g){
printf("0\n");
} else {
bfs(s, u, d);
}
}
