사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
입력
첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.
출력
첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.
탐색을 고슴도치가 있는 곳에서도 해야 하고 물이 번져 나가는 곳에서도 해야 해요. 이때 고슴도치는 물이 있는 곳으로 갈 수 없다는 규칙과 물이 찰 예정인 지역으로 이동할 수 없다는 규칙이 있어요. 그러므로 맵에 물이 먼저 번져 나가는 것을 표현시킨 다음 고슴도치를 이동시켜야 해요. 이때 탐색을 할 때 방문할 수 있는 지역을 모두 방문하게 된다면 물을 먼저 탐색시켰을 때 빈공간을 찾아서 전부 물로 바꿔 버리기 때문에 미리 방문 시작할 좌표를 q에 담아놓고 탐색을 시작하기 전 q에 들어간 원소의 개수를 미리 구해놓은 다음 나중에 방문하며 추가로 방문할 수 있는 지역이 있어 원소를 추가하더라도해당 시간에 탐색해야 하는 곳까지만 하게 구현 해야 해요. 고슴도치의 이동도 같은 구조예요.
0초
1초2초
이렇게 각 한 번씩 탐색을 했을 때마다 시간을 증가시켜서 최종 시간을 구하게 해요. 물이 탐색을 시작할 때 해당 위치에 고슴도치가 있으면 이때 부터는 굳이 물이 번지는 것을 구현할 필요가 없어요. 이미 이 순간부터는 물은 고슴도치를 위협할 수 있는 위치에 없다는 것이니까요.
4. 함수 설명
MoveWater() : 물 좌표가 들어있는 q를 상하좌우 탐색하며 물이 번져 나가는 것을 구현하는 함수예요.
MoveS() : 고슴도치의 이동을 구현해주는 함수예요. 고슴도치가 이동을 하기 전 MoveWater()를 호출하여 물이 먼저 움직인 다음 이동하게 했어요.
5. 코드
#define MAX 50 + 1
#define X second
#define Y first
#include <iostream>
#include <queue>
using namespace std;
// 상하좌우
int dx[4] = { 0, 0,-1, 1 };
int dy[4] = { 1, -1, 0, 0 };
char map[MAX][MAX];
int R, C;
queue < pair<int, int>> sq;
queue < pair<int, int>> wq;
void MoveWater()
{
int cnt = wq.size();
for (int i = 0; i < cnt; i++)
{
pair<int, int> cur = wq.front();
wq.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (ny < 0 || nx < 0 || ny >= R || nx >= C)
continue;
if (map[ny][nx] != '.')
continue;
map[ny][nx] = '*';
wq.push({ny, nx});
}
}
}
int MoveS()
{
int time = 0;
while (!sq.empty())
{
time++;
MoveWater();
int cnt = sq.size();
for (int i = 0; i < cnt; i++)
{
pair<int, int> cur = sq.front();
sq.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (ny < 0 || nx < 0 || ny >= R || nx >= C)
continue;
if (map[ny][nx] == 'D')
return time;
if (map[ny][nx] != '.')
continue;
map[ny][nx] = 'S';
sq.push({ny, nx});
}
}
}
return -1;
}
int main()
{
cin >> R >> C;
for (int y = 0; y < R; y++)
{
for (int x = 0; x < C; x++)
{
cin >> map[y][x];
if (map[y][x] == 'S')
sq.push({ y, x });
else if (map[y][x] == '*')
wq.push({y, x});
}
}
int time = MoveS();
if (time == -1)
cout << "KAKTUS" << endl;
else
cout << time << endl;
return 0;
}
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
'.': 빈 공간
'#': 벽
'@': 상근이의 시작 위치
'*': 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
BOJ 3055랑 아주 유사한 문제였어요. 풀이 과정이 완전 똑같았어요. 한 턴마다 불과 상근이가 이동해야 하고 불이 먼저 번져 나간 이후에 상근이가 이동해야 문제에서 요구하는 조건인 불이 붙으려는 칸으로 이동할 수 없다를 만족하게 돼요. 그래서 이문제도 q를 2개 구현했고 각각 탐색을 하기 전 미리 q에 들어가 있는 좌표의 개수를 구해놓은 다음 해당 턴에는 탐색을 시작 하기 전 들어 있는 좌표만 탐색하게 진행하게 했어요.
이 문제는 도착 좌표가 따로 정해져 있지 않고 맵을 벗어나게 되면 탈출이라는 규칙을 갖고 있었기에 탐색 범위가 맵을 벗어났을 때 탈출했다는 조건을 줘야 해요.
0초
1초
2초
이제 다음 탐색에 상근이 위치로 불이 번질 텐데 상근이는 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다는 규칙이 있기에 이 순간부터 불은 상근이를 잡을 수가 없어요. 그래서 불은 더 이상 탐색하지 않아요.
3초4초5초(탈출 성공)
4. 함수 설명
MoveFire : 불이 번져 나가는 것을 구현해주는 함수예요.
MoveS : 상근이가 이동하는 함수예요. 탐색 전 MoveFire 를 호출하여 불이 먼저 움직인 다음 상근이가 움직이게 했어요.
5. 코드
#define MAX 1000 + 1
#define X second
#define Y first
#include <iostream>
#include <queue>
using namespace std;
// 상하좌우
int dx[4] = { 0, 0,-1, 1 };
int dy[4] = { 1, -1, 0, 0 };
char map[MAX][MAX];
int w, h;
queue < pair<int, int>> sq;
queue < pair<int, int>> fq;
void MoveFire()
{
int cnt = fq.size();
for (int i = 0; i < cnt; i++)
{
pair<int, int> cur = fq.front();
fq.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (ny < 0 || nx < 0 || ny >= h || nx >= w)
continue;
if (map[ny][nx] != '.')
continue;
map[ny][nx] = '*';
fq.push({ ny, nx });
}
}
}
int MoveS()
{
int time = 0;
while (!sq.empty())
{
time++;
MoveFire();
int cnt = sq.size();
for (int i = 0; i < cnt; i++)
{
pair<int, int> cur = sq.front();
sq.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (ny < 0 || nx < 0 || ny >= h || nx >= w)
return time;
if (map[ny][nx] != '.')
continue;
map[ny][nx] = '@';
sq.push({ ny, nx });
}
}
}
return -1;
}
void Reset(int w, int h)
{
for (int y = 0; y < h; y++)
{
for (int x = 0; x < w; x++)
{
map[y][x] = '.';
}
}
while (!sq.empty())
sq.pop();
while (!fq.empty())
fq.pop();
}
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
cin >> w >> h;
for (int y = 0; y < h; y++)
{
for (int x = 0; x < w; x++)
{
cin >> map[y][x];
if (map[y][x] == '@')
sq.push({ y, x });
else if (map[y][x] == '*')
fq.push({ y, x });
}
}
int time = MoveS();
if (time == -1)
cout << "IMPOSSIBLE" << endl;
else
cout << time << endl;
Reset(w, h);
}
return 0;
}
당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.
당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?
입력
입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.
그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.
출력
각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.
3차원 문제라 방향 벡터를 기존에 상하좌우에서 위층, 아래층까지 추가 해줘야 하는 문제였어요. bfs 탐색을 사용하면 시작 지점부터 각 위치까지 도달할 수 있는 시간을 맵에 표현할 수 가 있는데 이 방법을 사용하기 위해서 맵을 문자가 아닌 숫자로 구현했어요.
.(빈공간) => 0
#(벽) => 1
E(탈출지점) => 2
S(시작지점) => 3
빈공간, 벽, 탈출지점을 표현하느라 시작 지점이 3부터 시작하게 되는데 이러면 맵이 이런 식으로 구현이 돼요.
맵이 구현이 되었다면 0인 지점만 탐색하게 진행하고 2인 지점을 찾게 되면 탈출할 수 있는 것이므로 2인 지점을 찾은 바로 전 지점에서 시간이 1 늘어 날 것이고 처음에 맵을 표현하느라 3부터 시작 했기 때문에 출발지에서 각 지점까지 도착하는데 걸리는 시간은 해당 지점 값 - 3이 되게 될 텐데 제 코드에서는 마지막 도착지는 방문처리를 하지 않고 찾기만 했을 때 바로 시간을 반환시킬 것이기 때문에 -2를 해주면 정답이 돼요.
4. 함수 설명
Reset : 테스트 케이스가 여러 개 일 수가 있는데 이때 이전에 있던 데이터들이 남아 있으면 새로운 테스트가 정상적으로 작동하지 않기 때문에 맵과 큐를 비워주는 함수예요.
5. 코드
#define MAX 30 + 1
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct pos
{
int l, r, c;
};
// 상하좌우 위층, 아래층
int dx[6] = { 0, 0,-1, 1 , 0, 0};
int dy[6] = { 1, -1, 0, 0, 0, 0};
int dl[6] = { 0, 0, 0, 0, 1, -1};
int map[MAX][MAX][MAX];
int L, R, C;
queue <pos> q;
int Bfs()
{
while (!q.empty())
{
pos cur = q.front();
q.pop();
// 상하좌우 위층, 아래층
for (int dir = 0; dir < 6; dir++)
{
int nc = cur.c + dx[dir];
int nr = cur.r + dy[dir];
int nl = cur.l + dl[dir];
if (nr < 0 || nc < 0 || nl < 0 || nr >= R || nc >= C || nl >= L)
continue;
if (map[nl][nr][nc] == 2)
return map[cur.l][cur.r][cur.c];
if (map[nl][nr][nc] != 0)
continue;
map[nl][nr][nc] = map[cur.l][cur.r][cur.c] + 1;
q.push({ nl, nr, nc });
}
}
return -1;
}
void Reset()
{
for (int l = 0; l < L; l++)
{
for (int r = 0; r < R; r++)
{
for (int c = 0; c < C; c++)
{
map[l][r][c] = '.';
}
}
}
while (!q.empty())
q.pop();
}
int main()
{
// #벽, . 빈칸, S 시작 지점, E 출구
while(true)
{
cin >> L >> R >> C;
if (L == 0)
break;
for (int l = 0; l < L; l++)
{
for (int r = 0; r < R; r++)
{
for (int c = 0; c < C; c++)
{
char ch;
cin >> ch;
if (ch == '.')
map[l][r][c] = 0;
else if (ch == '#')
map[l][r][c] = 1;
else if (ch == 'E')
map[l][r][c] = 2;
else if(ch == 'S')
{
map[l][r][c] = 3;
q.push({ l, r, c });
}
}
}
}
int time = Bfs();
if (time == -1)
cout << "Trapped!" << endl;
else
cout << "Escaped in " << time - 2 << " minute(s)." << endl;
Reset();
}
return 0;
}
눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.
예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.
<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.
M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.
출력
첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.
입력에서 주어지는 좌표를 기준으로 맵에 영역을 표시하고 최종적으로 맵에 영역이 표시가 안 된 구역의 수와 각 구역의 넓이를 구하는 문제였어요. 일단 주어진 좌표를 기준으로 맵에만 제대로 표시한다면 이후에는 DFS, BFS 등을 이용하여 탐색을 하면 문제가 요구하는 각 영역의 개수와 넓이를 구할 수 있게 돼요.
입력 예시가 보면 0 2 4 4 이런 식으로 주어지는데 이건 0,2 좌표부터 4,4 좌표까지 맵에 그리라는 건데 이걸 그대로 코드에 바로 사용할 순 없었어요.
맵에서 주어지는 좌표는 이렇게 각 꼭 짓점의 좌표를 주는 건데 제가 맵 배열을 관리할 때 각 좌표는
이렇게 되기 때문이에요.
만약 입력에서 주어지는 좌표를 기준으로 x2, y2 좌표에서 단순히 -1 만 해서 맵에 그려주게 되면 원하는 그림이 나와요.
그래서 입력으로 주어지는 꼭짓점 좌표를 이용해서 맵에 표시를 해주기 위해서 다음과 같은 코드를 사용했어요.
4.코드
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define X first
#define Y second
#define MAX 100 + 1
int N, M, K;
// 상하좌우
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int map[MAX][MAX];
int visit[MAX][MAX];
int Dfs(int x, int y)
{
int cnt = 1;
stack<pair<int, int>> s;
s.push({x , y});
visit[x][y] = 1;
while (!s.empty())
{
pair<int, int> cur = s.top();
s.pop();
if (visit[cur.X][cur.Y] == 0)
cnt++;
visit[cur.X][cur.Y] = 1;
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (map[nx][ny] == 1 || visit[nx][ny] == 1)
continue;
s.push({ nx, ny });
}
}
return cnt;
}
int main()
{
vector<int> v;
// M 세로 N 가로
cin >> M >> N >> K;
for (int i = 0; i < K; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int y = y1; y < y2; y++)
{
for (int x = x1; x < x2; x++)
{
map[x][y] = 1;
}
}
}
for (int y = M - 1; y >= 0; y--)
{
for (int x = 0; x < N; x++)
{
if (map[x][y] == 0 && visit[x][y] == 0)
{
v.push_back(Dfs(x, y));
}
}
}
sort(v.begin(), v.end());
cout << v.size() << endl;
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
return 0;
}
탐색알고리즘만 알고 있다면 쉽게 풀 수 있는 문제였어요. 저 같은 경우는 맵 0, 0 좌표부터 탐색을 시작하여 쓰레기가 발견되면 그 지점부터 DFS 탐색을 시작해 주변 지역에 있는 쓰레기 범위를 구하여 result 변수에 저장하여 모든맵 탐색을 끝냈을 때 가장 최댓값을 구하는 방식으로 해결했어요.
4. 코드
#include <iostream>
#include <stack>
#define X first
#define Y second
#define MAX 100 + 2
using namespace std;
int map[MAX][MAX];
int visit[MAX][MAX];
// 상 하 좌 우
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
// N : 세로 길이, M : 가로 길이, K : 쓰레기의 개수
int N, M, K;
int result;
void Dfs(int x, int y)
{
int cnt = 1;
stack<pair<int, int>> s;
s.push({x, y});
visit[x][y] = 1;
while (!s.empty())
{
pair<int, int> cur = s.top();
s.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 1 || ny < 1 || nx > M || ny > N)
continue;
if (visit[nx][ny] == 1 || map[nx][ny] == 0)
continue;
s.push({nx, ny});
visit[nx][ny] = 1;
cnt++;
}
}
if (result < cnt)
result = cnt;
}
int main()
{
cin >> N >> M >> K;
// 맵 정보 입력
// 쓰레기가 있는곳 좌표만 1로 설정
for (int i = 0; i < K; i++)
{
int x, y;
// 입력을 y , x로 줌
cin >> y >> x;
map[x][y] = 1;
}
for (int y = 1; y <= N; y++)
{
for (int x = 1; x <= M; x++)
{
if (visit[x][y] == 0 && map[x][y] == 1)
{
Dfs(x, y);
}
}
}
cout << result;
return 0;
}
가장 최근 커밋에 보면 원하지않은 파일 삭제가 있었는데 해당 파일을 살리기 위하여 일단 해당 커밋을 [Revert changes in commit...버튼을 눌렀어요. 해당 버튼을 누르니까 바로 아래 커밋했을떄로 돌아가더라고요.
그럼 이 커밋을 Undo 할 수 있는 버튼이 생겨요.
이걸 Undo를 하면 이런 상태가 돼요
그럼 당연하게도 커밋한 내용 중 추가한 건 삭제 처리가 될 거고 삭제한 건 추가 처리가 될 거예요
저는 삭제 됐던 파일들은 복구하고 새로 추가한 파일들은 그대로 추가를 해야 하므로 추가된 파일을 삭제한 기록을 [Discard Changes] 해줬어요.
푸쉬까지 하면 실수로 삭제한 파일이 복구된 게 서버에 반영된걸 볼 수 있어요.
지금 같은 경우는 가장 최근에 커밋에서 문제가 발생해서 비교적 쉽게 해결했지만 커밋이 쌓인 상태에서 파일을 복구할 때는 해당 시점으로 간 후 복구할 파일을 따로 파일로 저장해놓은 다음 최신 버전으로 돌아와서 추가하는 식으로 해야 할 거 같아요. 깃을 항상 최신 상태로 유지해야 할 것 같아요.
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.
플로이드 워셜을 이용하면 쉽게 풀 수 있는 문제인데 DFS로도 풀 수 있는 문제였어요. 0번째 노드부터 DFS 탐색을 시작하는데 해당 노드에 방문 했을 때 갈 수 있는 경로가 있다면 계속 DFS 탐색을 하며 최종적으로 갈 수 있는 모든 경로를 찾을 수 있게 돼요. 첫번째 예제로 설명을 드리면 탐색 순서가 0 => 1 => 2 순서로 탐색을 하는것을 할수있어요.
예제1
예제 2에 3번노드의 탐색을 시각화 해볼게요.
이런 식으로 0번 노드부터 N-1번 노드까지 탐색을 하면 연결 여부를 알 수 있게 돼요.
4. 함수 설명
void reset() 잠기는 높이가 바뀔때마다 bfs 탐색을 다시 하기 위해서 visited을 초기화 해줘요.
5. 코드
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#define MAX 100 + 1
using namespace std;
int N;
vector<int>graph[MAX];
int visit[MAX];
void Reset()
{
// memset(visit, 0, sizeof(visit));
// 위코드와 같은 역할
for (int i = 0; i < N; i++)
{
visit[i] = 0;
}
}
void Dfs(int node)
{
stack<int> s;
s.push(node);
while (!s.empty())
{
int cur = s.top();
s.pop();
// 해당 노드가 가지고 있는 경로만큼 탐색
for (int i = 0; i < graph[cur].size(); i++)
{
// 이미 방문을 했다면 스킵하기
if (visit[graph[cur][i]] == 1)
continue;
visit[graph[cur][i]] = 1;
s.push(graph[cur][i]);
}
}
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
int path;
cin >> path;
// 해당 위치로 가는 경로가 있다면
if (path == 1)
graph[i].push_back(j);
}
}
for (int i = 0; i < N; i++)
{
// 각 노드마다 방문여부 초기화 해주고
Reset();
// 순서대로 방문가능한곳부터 dfs 탐색 시작
Dfs(i);
for (int j = 0; j < N; j++)
cout << visit[j] << " ";
cout << "\n";
}
}
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.
어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.
이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.
물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).
또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.
이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.
어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.
입력
첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.
잠기는 영역이 바뀔 때마다 안전 구역이 달라지기 때문에 잠기는 영역을 1부터 모두 검사하면서 찾아야 하는 문제라고 생각이 됐어요. 그래서 최대 높이 변수를 입력받을 때 저장한 다음 최대 높이부터 1씩 내려가며 모든 경우를 탐색해서 최대로 나올 수 있는 안전 구역을 구했어요.
탐색 과정을 눈으로 보여드리기 위해 첫번째 테스트케이스에 잠긴높이가 5일때 기준으로 가시화 해봤어요.
0,0 부터 탐색을 시작하며 잠긴높이보다 높은 6부터 탐색을 시작해서 안전 영역을 구해여.
4. 함수 설명
void reset() 잠기는 높이가 바뀔때마다 bfs 탐색을 다시 하기 위해서 visited을 초기화 해줘요.
5. 코드
#define _CRT_SECURE_NO_WARNINGS
#define X first
#define Y second
#define MAX 100+1
#include <iostream>
#include <queue>
using namespace std;
int visited[MAX][MAX];
int map[MAX][MAX];
// 동서남북
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
// N : 맵 크기
int N;
int safetyArea;
queue<pair<int, int>> q;
void bfs(int height)
{
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
visited[cur.X][cur.Y] = 1;
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
// 배열 범위 벗어나는지 체크
if (nx < 0 || nx >= N || ny < 0 || ny >= N)
continue;
// 방문할 지역의 높이가 잠긴 구역보다 낮다면 안전 구역이 아니므로 생략
if (map[nx][ny] <= height || visited[nx][ny] == 1)
continue;
visited[nx][ny] = 1;
q.push({ nx, ny });
}
}
}
void reset()
{
safetyArea = 0;
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
visited[x][y] = 0;
}
}
}
int main()
{
int height = 0, result = 0;
ios::sync_with_stdio(0);
cin.tie(0);
scanf("%d", &N);
// M : 가로길이, N : 세로 길이
// 맵 정보 입력
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
scanf("%d", &map[x][y]);
if (height < map[x][y])
height = map[x][y];
}
}
while (height >= 0)
{
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
// 잠긴 높이보다 지역 높이가 크다면 안전 구역이므로 탐색 시작
if (map[x][y] > height && visited[x][y] == 0)
{
q.push({ x, y });
bfs(height);
safetyArea++;
}
}
}
if (result < safetyArea)
result = safetyArea;
reset();
height--;
}
printf("%d", result);
return 0;
}
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Events;
public class Player : MonoBehaviour
{
public float moveSpeed;
private Coroutine moveRoutine;
public UnityAction<Vector2Int, Vector2Int> onDecideTargetTile;
private void Update()
{
// 마우스 왼쪽버튼 클릭시
if (Input.GetMouseButtonDown(0))
{
// 마우스 클릭시 좌표를 인게임 좌표로 변환하여 mousePos 변수에 저장
Vector3 mousePos = Camera.main.ScreenToWorldPoint(Input.mousePosition);
// z값은 사용을 안하므로 x, y 값만 저장후 Move
int targetPosX = (int)Math.Truncate(mousePos.x);
int targetPosY = (int)Math.Truncate(mousePos.y);
int currentPosX = (int)Math.Round(this.transform.position.x);
int currentPosY = (int)Math.Round(this.transform.position.y);
Vector2Int curPos = new Vector2Int(currentPosX, currentPosY);
Vector2Int targetPos = new Vector2Int(targetPosX, targetPosY);
Debug.LogFormat("curPos : {0}, targetPos : {1}", curPos, targetPos);
this.onDecideTargetTile(curPos, targetPos);
}
}
// 플레이어 이동 스크립트
// 매개변수 pathList를 입력받아 경로 단위로 움직입니다.
public void Move(List<Vector3> pathList)
{
if (this.moveRoutine != null)
this.StopCoroutine(moveRoutine);
moveRoutine = this.StartCoroutine(this.MoveRoutine(pathList));
}
private IEnumerator MoveRoutine(List<Vector3> pathList)
{
int pathCount = pathList.Count;
for (int index = 1; index < pathList.Count; index++)
{
if (pathCount < 1)
break;
while (true)
{
// dir(방향) = 타겟방향 - 플레이어 현재 위치
var dir = pathList[index] - this.transform.position;
this.transform.Translate(dir.normalized * this.moveSpeed * Time.deltaTime);
// 타겟위치와 현재위치의 거리차이가 0.1이하가 될시 while문 빠져나옵니다
var distance = dir.magnitude;
if (distance <= 0.1f)
break;
yield return null;
}
}
// move루틴 끝났으므로 null로 초기화
this.moveRoutine = null;
}
}
Main.cs
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.Events;
public class Main : MonoBehaviour
{
private MapManager mapManager;
private Player player;
void Start()
{
this.player = GameObject.FindObjectOfType<Player>();
this.mapManager = GameObject.FindObjectOfType<MapManager>();
this.player.onDecideTargetTile = (startPos, targetPos) =>
{
this.mapManager.PathFinding(startPos, targetPos);
this.player.Move(this.mapManager.PathList);
};
}
}
MapManager.cs
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class MapManager : MonoBehaviour
{
public class Node
{
public Node(bool _isWall, int _x, int _y) { isWall = _isWall; x = _x; y = _y; }
public bool isWall;
public Node ParentNode;
// G : 시작으로부터 이동했던 거리, H : |가로|+|세로| 장애물 무시하여 목표까지의 거리, F : G + H
public int x, y, G, H;
public int F { get { return G + H; } }
}
private GridLayout gridMap;
int sizeX, sizeY;
Node[,] NodeArray;
Node StartNode, TargetNode, CurNode;
List<Node> OpenList, ClosedList;
public Vector2Int bottomLeft, topRight;
private List<Node> FinalNodeList;
public bool allowDiagonal, dontCrossCorner;
public List<Vector3> PathList
{
get; private set;
}
private void Start()
{
this.gridMap = GameObject.Find("GridMap").GetComponent<GridLayout>();
this.PathList = new List<Vector3>();
}
public void PathFinding(Vector2Int startPos, Vector2Int targetPos)
{
this.PathList.Clear();
// 캡크기 설정
// NodeArray의 크기 정해주고, isWall, x, y 대입
sizeX = topRight.x - bottomLeft.x + 1;
sizeY = topRight.y - bottomLeft.y + 1;
NodeArray = new Node[sizeX, sizeY];
// 장애물 감지
// 맵에 Layer가 Wall인 태그를 가진 오브젝트가 있는지 검사하고 있을시 지나갈수없는 통로로 설정한다.
for (int i = 0; i < sizeX; i++)
{
for (int j = 0; j < sizeY; j++)
{
bool isWall = false;
foreach (Collider2D col in Physics2D.OverlapCircleAll(new Vector2(i + bottomLeft.x + 0.5f, j + bottomLeft.y + 0.5f), 0.4f))
{
if (col.gameObject.layer == LayerMask.NameToLayer("Wall")) isWall = true;
}
NodeArray[i, j] = new Node(isWall, i + bottomLeft.x, j + bottomLeft.y);
}
}
// 시작과 끝 노드, 열린리스트와 닫힌리스트, 마지막리스트 초기화
StartNode = NodeArray[startPos.x - bottomLeft.x, startPos.y - bottomLeft.y];
TargetNode = NodeArray[targetPos.x - bottomLeft.x, targetPos.y - bottomLeft.y];
OpenList = new List<Node>() { StartNode };
ClosedList = new List<Node>();
FinalNodeList = new List<Node>();
while (OpenList.Count > 0)
{
// 열린리스트 중 가장 F가 작고 F가 같다면 H가 작은 걸 현재노드로 하고 열린리스트에서 닫힌리스트로 옮기기
CurNode = OpenList[0];
for (int i = 1; i < OpenList.Count; i++)
if (OpenList[i].F <= CurNode.F && OpenList[i].H < CurNode.H) CurNode = OpenList[i];
OpenList.Remove(CurNode);
ClosedList.Add(CurNode);
// 마지막
if (CurNode == TargetNode)
{
Node TargetCurNode = TargetNode;
while (TargetCurNode != StartNode)
{
FinalNodeList.Add(TargetCurNode);
TargetCurNode = TargetCurNode.ParentNode;
}
FinalNodeList.Add(StartNode);
FinalNodeList.Reverse();
for (int i = 0; i < FinalNodeList.Count; i++)
{
//print(i + "번째는 " + FinalNodeList[i].x + ", " + FinalNodeList[i].y);
Vector3 path = new Vector3(FinalNodeList[i].x, FinalNodeList[i].y, 0);
this.PathList.Add(path);
}
return;
}
// ↗↖↙↘
if (allowDiagonal)
{
OpenListAdd(CurNode.x + 1, CurNode.y + 1);
OpenListAdd(CurNode.x - 1, CurNode.y + 1);
OpenListAdd(CurNode.x - 1, CurNode.y - 1);
OpenListAdd(CurNode.x + 1, CurNode.y - 1);
}
// ↑ → ↓ ←
OpenListAdd(CurNode.x, CurNode.y + 1);
OpenListAdd(CurNode.x + 1, CurNode.y);
OpenListAdd(CurNode.x, CurNode.y - 1);
OpenListAdd(CurNode.x - 1, CurNode.y);
}
}
void OpenListAdd(int checkX, int checkY)
{
// 상하좌우 범위를 벗어나지 않고, 벽이 아니면서, 닫힌리스트에 없다면
if (checkX >= bottomLeft.x && checkX < topRight.x + 1 && checkY >= bottomLeft.y && checkY < topRight.y + 1 && !NodeArray[checkX - bottomLeft.x, checkY - bottomLeft.y].isWall && !ClosedList.Contains(NodeArray[checkX - bottomLeft.x, checkY - bottomLeft.y]))
{
// 대각선 허용시, 벽 사이로 통과 안됨
if (allowDiagonal) if (NodeArray[CurNode.x - bottomLeft.x, checkY - bottomLeft.y].isWall && NodeArray[checkX - bottomLeft.x, CurNode.y - bottomLeft.y].isWall) return;
// 코너를 가로질러 가지 않을시, 이동 중에 수직수평 장애물이 있으면 안됨
if (dontCrossCorner) if (NodeArray[CurNode.x - bottomLeft.x, checkY - bottomLeft.y].isWall || NodeArray[checkX - bottomLeft.x, CurNode.y - bottomLeft.y].isWall) return;
// 이웃노드에 넣고, 직선은 10, 대각선은 14비용
Node NeighborNode = NodeArray[checkX - bottomLeft.x, checkY - bottomLeft.y];
int MoveCost = CurNode.G + (CurNode.x - checkX == 0 || CurNode.y - checkY == 0 ? 10 : 14);
// 이동비용이 이웃노드G보다 작거나 또는 열린리스트에 이웃노드가 없다면 G, H, ParentNode를 설정 후 열린리스트에 추가
if (MoveCost < NeighborNode.G || !OpenList.Contains(NeighborNode))
{
NeighborNode.G = MoveCost;
NeighborNode.H = (Mathf.Abs(NeighborNode.x - TargetNode.x) + Mathf.Abs(NeighborNode.y - TargetNode.y)) * 10;
NeighborNode.ParentNode = CurNode;
OpenList.Add(NeighborNode);
}
}
}
void OnDrawGizmos()
{
if (FinalNodeList == null)
return;
if (FinalNodeList.Count != 0)
{
for (int i = 0; i < FinalNodeList.Count - 1; i++)
{
Gizmos.DrawLine(new Vector2(FinalNodeList[i].x + 0.5f, FinalNodeList[i].y + 0.5f), new Vector2(FinalNodeList[i + 1].x + 0.5f, FinalNodeList[i + 1].y + 0.5f));
}
}
}
}
7. 처음 영역을 잡은 오브젝트에 작성한 스크립트와 Image, Button컴포넌트를 추가해줘요.
Image는 Raycast Target을 이용해 클릭이벤트를 가져오기위해서 넣는것이기 때문에 컬러 알파값을0으로 빼줘요.
UISkillBtn.cs
using System.Collections;
using UnityEngine;
using UnityEngine.UI;
using TMPro;
namespace UISkillBtnExam
{
public class UISkillBtn : MonoBehaviour
{
public Button btn;
public float coolTime = 10f;
public TMP_Text textCoolTime;
private Coroutine coolTimeRoutine;
public Image imgFill;
public void Init()
{
this.textCoolTime.gameObject.SetActive(false);
this.imgFill.fillAmount = 0;
}
// Start is called before the first frame update
void Start()
{
this.btn = this.GetComponent<Button>();
this.btn.onClick.AddListener(() =>
{
if (this.coolTimeRoutine != null)
{
Debug.Log("쿨타임 중입니다...");
}
else
{
this.coolTimeRoutine = this.StartCoroutine(this.CoolTimeRoutine());
}
});
Init();
}
private IEnumerator CoolTimeRoutine()
{
Debug.Log(textCoolTime);
this.textCoolTime.gameObject.SetActive(true);
var time = this.coolTime;
while (true)
{
time -= Time.deltaTime;
this.textCoolTime.text = time.ToString("F1");
var per = time / this.coolTime;
//Debug.Log(per);
this.imgFill.fillAmount = per;
if (time <= 0)
{
this.textCoolTime.gameObject.SetActive(false);
break;
}
yield return null;
}
this.coolTimeRoutine = null;
}
}
}
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
예를 들어 위와 같은 이진 트리가 입력되면,
전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.
입력
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
출력
첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
예제 입력 1복사
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .
예제 출력 1복사
ABDCEFG
DBAECFG
DBEGFCA
3. 풀이 과정
C++에서 제공하는 map(key, value)형태의 자료구조로 트리를 구현해서 풀어봤어요.
4. 함수 설명
preOreder(), inOrder, postOreder() 세함수 모두 재귀호출로 작동하며 출력순서만 차이가 있어요.
출력순서 = 데이터를 처리하는 순서
5. 코드
#pragma warning(disable:4996)
#include <iostream>
#include <map>
using namespace std;
struct Node
{
char left;
char right;
};
// 맵으로 트리 구현
map<char, Node> m;
// 전위 순회
void preOrder(char node)
{
// root - left - right
if (node == '.') return;
printf("%c", node);
preOrder(m[node].left);
preOrder(m[node].right);
}
// 중위 순회
void inOrder(char node)
{
// left - root - right
if (node == '.') return;
inOrder(m[node].left);
printf("%c", node);
inOrder(m[node].right);
}
// 후위 순회
void postOrder(char node)
{
// left - right - root
if (node == '.') return;
postOrder(m[node].left);
postOrder(m[node].right);
printf("%c", node);
}
int main()
{
int n;
scanf("%d", &n);
char node, left, right;
// 트리 입력받기
for (int i = 0; i < n; i++)
{
cin >> node >> left >> right;
m[node].left = left;
m[node].right = right;
// m.insert({ node, {left, right} }); 위와 같다.
}
preOrder('A');
printf("\n");
inOrder('A');
printf("\n");
postOrder('A');
return 0;
}
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
그래서 이러한 성질을 이용해서 익은 토마토가 있는 시점부터 1씩 해당 지역에 값을 1씩 증가시켜주면 해당 지역에 있는 토마토가 익는 데까지 걸린 소요일-1의 값을 구할 수 있어요. 문제에서는 모든 토마토가 익는 데까지 수요일을 구하라고 하였으니 탐색을 할 때마다 해당 지역에 있는 토마토가 익는 데까지 걸린 수요일을 비교하며 최댓값을 찾아 -1을 해주면 문제에서 요구하는 답을 구할 수 있어요.
4. 함수 설명
check() : BFS 탐색을 끝낸 후에도 안 익은 토마토가 있는지 확인하며 안 익은 토마토가 있으면 result 값을 0으로 초기화 해줘요.
5. 코드
#define _CRT_SECURE_NO_WARNINGS
#define X first
#define Y second
#define MAX 1000+1
#include <iostream>
#include <queue>
using namespace std;
int visited[MAX][MAX];
int map[MAX][MAX];
// 동서남북
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
// M : 가로길이, N : 세로 길이
int N, M;
int result;
queue<pair<int, int>> q;
// 맵에 안익은 토마토가 있는지 체크
void check()
{
for (int x = 0; x < N; x++)
{
for (int y = 0; y < M; y++)
{
if (map[x][y] == 0)
{
// 마지막에 --를 해주므로 0으로 초기화해서 안익은 토마토가 있을경우 -1값 유도
result = 0;
return;
}
}
}
}
void bfs()
{
while (!q.empty())
{
// q에 들어있는 토마토를 꺼내서 cur에 할당
pair<int, int> cur = q.front();
q.pop();
// 각 맵에는 익는데 까지 걸린 소요일-1 값을 갖고있으므로 q에서 꺼낸 토마토의 값을 비교하여 최대값 구하기
if (result < map[cur.X][cur.Y])
result = map[cur.X][cur.Y];
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
// 동서남북 탐색중 배추밭을 벗어나거나
if (nx < 0 || nx >= N || ny < 0 || ny >= M)
continue;
// 이미 방문을 했던곳이거나, 해당지역에 안익은 토마토가 없을경우 방문할 필요가 없으므로 방문처리 X
if (visited[nx][ny] == 1 || map[nx][ny] != 0)
continue;
visited[nx][ny] = 1;
// 방문할때마다 익게만든 토마토가 갖고있는값에서 1씩 더해줌
map[nx][ny] = map[cur.X][cur.Y] + 1;
// 방문한지역에도 익은 토마토가 새롭게 생겼으므로 q에 넣어주기
q.push({ nx, ny });
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
scanf("%d %d", &M, &N);
// M : 가로길이, N : 세로 길이
// 맵 정보 입력
for (int x = 0; x < N; x++)
{
for (int y = 0; y < M; y++)
{
scanf("%d", &map[x][y]);
// 맵 정보 입력중 토마토가 있을경우 q에 미리 넣어둔다.
if (map[x][y] == 1)
{
q.push({ x, y });
// q에 있는 지역은 반드시 방문을 할예정이므로 미리 방문체크
visited[x][y] = 1;
}
}
}
bfs();
check();
result--;
printf("%d", result);
return 0;
}
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
1
1
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.
동서남북으로 탐색을 진행하며 배추가 서로 인접되어있는 배추를 찾을때마다 방문처리를 해서 해당 지역을 다시 방문 하지 않음으로써 배추들의 그룹을 찾을수 있어요. BFS, DFS탐색을 한번씩 할때마다 한개의 그룹이 있는것 이므로 탐색을 한번씩 완료 할떄마다 배추흰지렁이수를 1씩 증가시켜주면 풀수 있는 문제였어요.
4. 함수 설명
reset() : 테스트 케이스가 여러개 이다 보니 테스트 케이스를 진행할때마다 배추밭 map배열과 방문자 처리용 visited배열을 초기화 해주는 함수에요.
5. 코드
#define _CRT_SECURE_NO_WARNINGS
#define X first
#define Y second
#define MAX 50+1
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int visited[MAX][MAX];
int map[MAX][MAX];
// T : 테스트 케이스 갯수, M : 배추밭의 가로 길이
// N : 배추밭의 세로 길이, K : 배추 갯수
int T, M, N, K;
// wormCnt : 배추흰지렁이
int wormCnt;
// 동서남북
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
// 테스트 케이스마다 배추밭맵, 방문처리맵 초기화
void reset()
{
wormCnt = 0;
for (int x = 0; x < N; x++)
{
for (int y = 0; y < M; y++)
{
map[x][y] = 0;
visited[x][y] = 0;
}
}
}
void dfs_stack(int x, int y)
{
stack<pair<int, int>> s;
// 출발 지점 방문처리
visited[x][y] = 1;
s.push({ x,y });
while (!s.empty())
{
pair<int, int> cur = s.top();
s.pop();
for (int dir = 0; dir < 4; dir++)
{
// nx = nextX, ny = nextY
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
// 동서남북 탐색중 배추밭을 벗어나거나
if (nx < 0 || nx >= N || ny < 0 || ny >= M)
continue;
// 이미 방문을 했던곳이거나, 해당지역에 배추가 없을경우 방문할 필요가 없으므로 방문처리 X
if (visited[nx][ny] == 1 || map[nx][ny] != 1)
continue;
visited[nx][ny] = 1;
s.push({nx, ny});
}
}
}
void bfs_queue(int x, int y)
{
queue<pair<int, int>> q;
// 출발 지점 방문처리
visited[x][y] = 1;
q.push({x,y});
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++)
{
// nx = nextX, ny = nextY
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
// 동서남북 탐색중 배추밭을 벗어나거나
if (nx < 0 || nx >= N || ny < 0 || ny >= M)
continue;
// 이미 방문을 했던곳이거나, 해당지역에 배추가 없을경우 방문할 필요가 없으므로 방문처리 X
if (visited[nx][ny] == 1 || map[nx][ny] != 1)
continue;
visited[nx][ny] = 1;
q.push({ nx, ny });
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
for (int t = 0; t < T; t++)
{
cin >> M >> N >> K;
reset();
// 배추밭 데이터 입력
for (int k = 0; k < K; k++)
{
int x, y;
cin >> x >> y;
// 입력 데이터와 맵 좌표를 맞추기위해 y x 바꿔주기
// ex 1 1 0
// 0 1 0
// 0 0 0
// (0,0), (0,1), (1,1)
map[y][x] = 1;
}
for (int x = 0; x < N; x++)
{
for (int y = 0; y < M; y++)
{
if (map[x][y] == 1 && visited[x][y] == 0)
{
//dfs_stack(x,y);
bfs_queue(x,y);
// 탐색이 끝날떄마다 배추흰지렁이 한마리씩 늘려주기
wormCnt++;
}
}
}
cout << wormCnt << endl;
}
return 0;
}
public sealed class DataManager
{
// 외부에서 접근 읽기 상태로만 접근할 수 있어 데이터 수정을 막고 데이터를 읽기만 할 수 있는 싱글톤 DataManager 선언
public static readonly DataManager instance = new DataManager();
// 딕셔너리로 데이터관리
private Dictionary<int, RawData> dicDatas = new Dictionary<int, RawData>();
private DataManager()
{
}
// json 데이터를 불러와서 딕셔너리에 저장하는 메소드
public void LoadData<T>(string path) where T : RawData
{
var json = File.ReadAllText(path);
T[] arr = JsonConvert.DeserializeObject<T[]>(json);
arr.ToDictionary(x => x.id).ToList().ForEach(x => dicDatas.Add(x.Key, x.Value));
}
// id 값으로 딕셔너리에서 검색하는 메소드
public T GetData<T>(int id) where T : RawData
{
var collection = this.dicDatas.Values.Where(x => x.GetType().Equals(typeof(T)));
return (T)collection.ToList().Find(x => x.id == id);
}
// 특정 데이터 그룹을 검색하고싶을대 해당 데이터 타입을 호출하면 해당 데이터타입 객체만 반환한다.
// ex(GetDatas<Student>()) = 딕셔너리에 저장된 데이터들중 Student타입을 가진 객체들만 반환
public IEnumerable<T> GetDatas<T>() where T : RawData
{
IEnumerable<RawData> col = this.dicDatas.Values.Where(x => x.GetType().Equals(typeof(T)));
return col.Select(x => (T)Convert.ChangeType(x, typeof(T)));
}
이때 당시에는 Datamanager에서 Json 데이터를 로드화는 과정에서 넣어야 하는 데이터의 타입과 Json데이터 파일 위치를 받아서 로드하는 과정을 가졌는데 이렇게 하면 데이터를 로드하는 과정이 아래처럼 나와요.
public class DataTest
{
public DataTest()
{
// json데이터를 불러와서 딕셔너리에 저장
DataManager.instance.LoadData<StudentData>("./student_data.json");
DataManager.instance.LoadData<StudyData>("./study_data.json");
DataManager.instance.LoadData<UserData>("./user_data.json");
}
}
이코드를 처음 사용할때는 문제점을 못느꼈는데 Unity에서 게임을 만들때 아래처럼 데이터가 로드되는 과정을 연출하고싶을때 문제가 되더라구요.
먼저 이런 연출을 하기 위해선 데이터파일의 총 갯수를 알아야 해요.
그래서 Datamanager에 데이터파일의 경로를 관리하는 리스트를 선언하고 데이터들의 경로가 담겨있는 데이터파일을 작성한다음 Init함수 에서 dataPathList에 데이터를 추가 해줬어요.
DatapathData.cs
public class DatapathData
{
public int id;
public string res_name;
public string type;
}
id는 중복값을 피하기 위함이고, res_name에는 데이터파일의 경로가 들어가요. type은 해당 json데이터들의 클래스를 적어줘요.
private IEnumerator LoadAllDataRoutine()
{
int idx = 0;
foreach (var data in this.dataPathList)
{
var path = string.Format("Datas/{0}", data.res_name);
ResourceRequest req = Resources.LoadAsync<TextAsset>(path);
yield return req;
float progress = (float)(idx + 1) / this.dataPathList.Count;
TextAsset asset = (TextAsset)req.asset;
LoadData<DataType>(asset.text);
yield return new WaitForSeconds(0.3f);
idx++;
}
yield return null;
}
자 이제 위에서 Init 함수를 정상적으로 작동 했다면 dataPathList에는 json 파일들의 경로가 저장되어 있어요.
리소스폴더 경로 + json파일의 경로를 해서 데이터의 Full 경로를 가져왔다면 이 경로로 Resource.LoadAsync<TextAsset>(풀경로)를 이용해서 ResourceRequest 데이터를 받아올수 있어요.
asset.text = json 데이터파일
ResourceRequest.asset은 바로 Newtonsoft의 JsonConvert로 역직렬화를 할수 없기 때문에 string형식을 지원하는 TextAsset.text를 사용하기 위해서 TextAsset형식으로 바꿔준다음 LoadData에 Json문자열을 넣고 를 호출해주면 되요
근데 이때 기존 LoadData를 사용하면 문제가 발생해요.
// json 데이터를 불러와서 딕셔너리에 저장하는 메소드
public void LoadData<T>(string json) where T : RawData
{
var datas = JsonConvert.DeserializeObject<T[]>(json);
datas.ToDictionary(x => x.id).ToList().ForEach(x => dicDatas.Add(x.Key, x.Value));
}
Json 문자열을 역직렬화한후에 딕셔너리에 넣는 과정에 데이터 타입을 알아야해서 <T> 동적으로 데이터타입을 받아야하는데 지금 코드로는 LoadData를 호출할때 데이터타입을 넣어줄수가 없어요. 동적으로 데이터타입을 받는 방법은 없을까? 알아보던중 해결방법이 담긴 링크를 찾았는데 자세히 이해는 못해서 링크만 남겨요.
private IEnumerator LoadAllDataRoutine()
{
int idx = 0;
foreach (var data in this.dataPathList)
{
var path = string.Format("Datas/{0}", data.res_name);
ResourceRequest req = Resources.LoadAsync<TextAsset>(path);
yield return req;
float progress = (float)(idx + 1) / this.dataPathList.Count;
this.onDataLoadComplete.Invoke(data.res_name, progress);
TextAsset asset = (TextAsset)req.asset;
var typeDef = Type.GetType(data.type);
this.GetType().GetMethod(nameof(LoadData))
.MakeGenericMethod(typeDef).Invoke(this, new string[] { asset.text });
idx++;
}
yield return null;
this.onDataLoadFinished.Invoke();
}
여기서 봐야하는부분이 LoadData를 호출하는 방법이 바꼈는데 Json 파일 데이터 경로를 넘기는 방법에서 직접 Json문자열을 넘기고 이때 데이터타입을 넘겨 줘야하는데 기존에는
public class DataTest
{
public DataTest()
{
// json데이터를 불러와서 딕셔너리에 저장
DataManager.instance.LoadData<StudentData>("./student_data.json");
DataManager.instance.LoadData<StudyData>("./study_data.json");
DataManager.instance.LoadData<UserData>("./user_data.json");
}
}
이런식으로 데이터 타입을 넘겨주었지만 이방법을 지금은 쓸수 없으니
var typeDef = Type.GetType(data.type);
this.GetType().GetMethod(nameof(LoadData))
.MakeGenericMethod(typeDef).Invoke(this, new string[] { asset.text });
데이터타입을 문자열로 먼저 저장해놓은 다음 Type.GetType으로 데이터타입을 받아온다음에 해당형식을 써주면
public void LoadData<T>(string json) where T : RawData
{
var datas = JsonConvert.DeserializeObject<T[]>(json);
datas.ToDictionary(x => x.id).ToList().ForEach(x => dicDatas.Add(x.Key, x.Value));
}
이렇게 데이터타입을 받을수 있게 됬어요.
이때 고민점은 DataManager가 아닌 외부에서는
public void LoadAllData()
{
App.instance.StartCoroutine(LoadAllDataRoutine());
}
이런식으로 LoadAllData 메소드를 통해서 LoadLoadAllDataRoutine 코루틴만 실행하면 정상적으로 모든데이터를 불러올수있어서 사실상 LoadData<T>를 외부에서 호출할 이유는 없어요. 그래서 private 으로 잠굴려고 했으나
외부에서는 처음에 Json데이터들의 타입과 주소를 저장하는 InIt메소드와 LoadAllData메소드만 호출함에도 불구하고 에러가 나오고 있는데 해결방법이 있으신분은 알려주세요.
DataManager.cs
using Newtonsoft.Json;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;
using UnityEngine.Events;
using System;
public class DataManager
{
public UnityEvent<string, float> onDataLoadComplete = new UnityEvent<string, float>();
public UnityEvent onDataLoadFinished = new UnityEvent();
public static readonly DataManager instance = new DataManager();
private Dictionary<int, RawData> dicDatas = new Dictionary<int, RawData>();
private List<DatapathData> dataPathList;
public void Init()
{
var datapath = "Datas/datapath_data";
var asset = Resources.Load<TextAsset>(datapath);
var json = asset.text;
var datas = JsonConvert.DeserializeObject<DatapathData[]>(json);
this.dataPathList = datas.ToList();
}
public void LoadData<T>(string json) where T : RawData
{
var datas = JsonConvert.DeserializeObject<T[]>(json);
datas.ToDictionary(x => x.id).ToList().ForEach(x => dicDatas.Add(x.Key, x.Value));
}
public void LoadAllData()
{
App.instance.StartCoroutine(LoadAllDataRoutine());
}
private IEnumerator LoadAllDataRoutine()
{
int idx = 0;
foreach (var data in this.dataPathList)
{
var path = string.Format("Datas/{0}", data.res_name);
ResourceRequest req = Resources.LoadAsync<TextAsset>(path);
yield return req;
float progress = (float)(idx + 1) / this.dataPathList.Count;
this.onDataLoadComplete.Invoke(data.res_name, progress);
TextAsset asset = (TextAsset)req.asset;
Debug.Log(req.asset);
var typeDef = Type.GetType(data.type);
this.GetType().GetMethod(nameof(LoadData))
.MakeGenericMethod(typeDef).Invoke(this, new string[] { asset.text });
yield return new WaitForSeconds(0.3f);
idx++;
}
yield return null;
this.onDataLoadFinished.Invoke();
}
// id 값으로 딕셔너리에서 검색하는 메소드
public T GetData<T>(int id) where T : RawData
{
var collection = this.dicDatas.Values.Where(x => x.GetType().Equals(typeof(T)));
return (T)collection.ToList().Find(x => x.id == id);
}
// 특정 데이터 그룹을 검색하고싶을대 해당 데이터 타입을 호출하면 해당 데이터타입 객체만 반환한다.
// ex(GetDatas<Student>()) = 딕셔너리에 저장된 데이터들중 Student타입을 가진 객체들만 반환
public IEnumerable<T> GetDataList<T>() where T : RawData
{
IEnumerable<RawData> col = this.dicDatas.Values.Where(x => x.GetType().Equals(typeof(T)));
return col.Select(x => (T)Convert.ChangeType(x, typeof(T)));
}
}
UnityEvent를 이용해서 데이터가 로드될때마다 이벤트를 호출하여 현재진행상황을 알려주어서 로딩씬 연출을 했어요.
지금은 데이터가 너무 적어서 너무 빠르게 진행되서 올라가는게 잘안보여서 중간에
yield return new WaitForSeconds(0.3f); 를써서 올라가는게 눈으로 보이게 테스트를 한 모습이에요.
using UnityEngine;
public class PlayerAction : MonoBehaviour
{
private Transform bulletSpawnPoint;
public GameObject bulletPrefab;
// Start is called before the first frame update
void Start()
{
// 플레이어 오브젝트에 자식오브젝트로 있는 BulletSpawnPoint 찾아와서 위치 설정 해주기
bulletSpawnPoint = this.transform.Find("BulletSpawnPoint");
}
// Update is called once per frame
void Update()
{
if (Input.GetKeyDown(KeyCode.Space))
{
//총알을 만든다
var bulletGo = Instantiate<GameObject>(this.bulletPrefab);
bulletGo.transform.position = this.bulletSpawnPoint.position;
}
}
}
Bullet.cs
using UnityEngine;
public class Bullet : MonoBehaviour
{
public float speed = 5f;
void Update()
{
// 총알이 많이 날라가면 삭제 해주기
if(this.transform.position.y > 5)
{
Destroy(this.gameObject);
}
// Vector3.up = new Vector(0, 1, 0)
this.transform.Translate(Vector3.up * this.speed * Time.deltaTime);
}
}
using UnityEngine;
public class PlayerMove : MonoBehaviour
{
public float speed = 1f;
void Update()
{
// 가로 이동 반환값 : LeftArrow = -1 RightArrow = 1
var h = Input.GetAxisRaw("Horizontal");
// 세로 이동 반환값 : DownArrow = -1 UpArrow = 1
var v = Input.GetAxisRaw("Vertical");
//단위 벡터 (크기가 1인 벡터)
var dir = new Vector3(h, v, 0).normalized;
this.transform.Translate(dir * this.speed * Time.deltaTime);
}
}
