[2021.03.29] 코딩테스트 연습
- isVisit처리 중요.
- DFS 스택을 사용해도 좋지만, 재귀함수를 이용하는 것이 생각이 편함.
- BFS는 Queue를 사용해, Queue가 빌때까지 동작...
음료수 얼려먹기 문제 풀이
DFS
#include <iostream>
using namespace std;
#define MAX_SIZE 5
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isVisit[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE] = {
{1, 1, 1, 1, 1},
{0, 0, 1, 1, 0},
{0, 0, 0, 1, 1},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0},
};
bool isValidXY(int x, int y)
{
if (x < 0)
return false;
if (y < 0)
return false;
if (x >= MAX_SIZE)
return false;
if (y >= MAX_SIZE)
return false;
if (map[x][y] == 1)
return false;
return true;
}
void dfs(int x, int y)
{
isVisit[x][y] = true;
int nx, ny;
for (int i = 0; i < 4; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (isValidXY(nx, ny)) {
if (isVisit[nx][ny] == false) {
dfs(nx, ny);
}
}
}
}
int main()
{
int cnt = 0;
for (int x = 0; x < MAX_SIZE; x++) {
for (int y = 0; y < MAX_SIZE; y++) {
if ((isVisit[x][y] == false) && (map[x][y] == 0)){
cnt++;
dfs(x, y);
}
}
}
cout << cnt << endl;
return 0;
}
BFS
#include <iostream>
#include <queue>
using namespace std;
#define MAX_SIZE 5
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool isVisit[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE] = {
{1, 1, 1, 1, 1},
{0, 0, 1, 1, 0},
{0, 0, 0, 1, 1},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0},
};
bool isValidXY(int x, int y)
{
if (x < 0)
return false;
if (y < 0)
return false;
if (x >= MAX_SIZE)
return false;
if (y >= MAX_SIZE)
return false;
if (map[x][y] == 1)
return false;
return true;
}
struct Point {
int x, y;
};
void bfs(int x, int y)
{
queue<Point> q;
isVisit[x][y] = true;
q.push({ x, y });
while (q.empty() == false) {
Point p = q.front();
q.pop();
int nx, ny;
for (int i = 0; i < 4; i++) {
nx = p.x + dx[i];
ny = p.y + dy[i];
if (isValidXY(nx, ny)) {
if (isVisit[nx][ny] == false) {
isVisit[nx][ny] = true;
q.push({ nx, ny });
}
}
}
}
}
int main()
{
int cnt = 0;
for (int x = 0; x < MAX_SIZE; x++) {
for (int y = 0; y < MAX_SIZE; y++) {
if ((isVisit[x][y] == false) && (map[x][y] == 0)) {
cnt++;
bfs(x, y);
}
}
}
cout << cnt << endl;
return 0;
}
Author And Source
이 문제에 관하여([2021.03.29] 코딩테스트 연습), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@comdori-web/2021.03.29-코딩테스트-연습저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)