오늘은 토요일,,, 어제 술을 너무 많이 먹고 실수를 해서 하루종일 기부니가 좋지않은 날이다.....
진짜 영어로 욕하고 싶은 날이다. 스윙스 맹키로;; 여 쉿! 음~ 여기까지
생각도 없앨겸 문제를 한문제 푸는데 문제를 풀면서도 계속 생각이 나고 마음이 진정이 되지 않았다.
하지만 문제는 1번 시도했는데 맞아버렸다;;;;; 그래도 기쁘지가 않았다. 앞으로 실수는 노노놉!!
이제 문제얘기로 돌아와서 이거 문제의 글이 제법 길어서 집중해서 읽어봤는데, 그냥 BFS이용해서 모두 탐색하면 되는것 같았다.
치즈가 놓여있지 않은 외벽부터 시작해서 0으로 되어있는 곳을 모두 탐색을 한다. 그리고 공기와 붙어있는 1을 0으로 바꿔준다. 이때 갱신하면서 오류가 날수있기 때문에 copy_board를 만들어줬는데, 흠 꼭 필요했나 싶기도 하다. 방문을 했는지 여부를 이용해서 해도 될것같았기 때문이다.
소스코드를 참고하고 언제나 피드백은 환영이다.
무엇보다 실수를 줄이자!! 쿄,,,,,,,,,,,,,,,,쿄
#include <iostream>
#include <queue>
using namespace std;
struct Que {
int x;
int y;
};
int board[102][102];
int copy_board[102][102];
bool vis[102][102];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
void board_initialize() {
for (int i = 0; i < 102; i++) {
for (int j = 0; j < 102; j++) {
board[i][j] = 0;
}
}
}
void vis_initialize() {
for (int i = 0; i < 102; i++) {
for (int j = 0; j < 102; j++) {
vis[i][j] = false;
}
}
}
void copy_initialize() {
for (int i = 0; i < 102; i++) {
for (int j = 0; j < 102; j++) {
copy_board[i][j] = 0;
}
}
}
void board_to_copy(int a, int b) {
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
copy_board[i][j] = board[i][j];
}
}
}
bool mission_success(int a, int b) {
bool success = true;
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
if (board[i][j] == 1) {
success = false;
break;
}
}
if (!success) break;
}
return success;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int a, b;
int time = 0;
int count = 0;
cin >> a >> b;
board_initialize();
copy_initialize();
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
cin >> board[i][j];
}
}
while (!mission_success(a,b)) {
board_to_copy(a, b);
vis_initialize();
queue<Que> Q;
Q.push({ 0,0 });
vis[0][0] = true;
while (!Q.empty()) {
auto cur = Q.front();
Q.pop();
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx < 0 or nx >= a or ny < 0 or ny >= b) continue;
if (copy_board[nx][ny] == 0 and vis[nx][ny] == false) {
Q.push({ nx,ny });
vis[nx][ny] = true;
} else if (copy_board[nx][ny] == 1 and vis[nx][ny] == false) {
board[nx][ny] = 0;
vis[nx][ny] = true;
}
}
}
time++;
}
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
if (copy_board[i][j] == 1) {
count++;
}
}
} // 마지막에 남은 치즈 칸 수 세기
cout << time << endl << count << endl;
}
//shout out to lynnnnnnnnn!
이 문제들은 현정이가 만들어놓은 문제집에서 골라 푸는건데 그 문제집에 있는 100문제를 다 풀고싶다.
단순히 코테를 준비하는 것이 아니라 재밌다 ㅋㅋㅋ 취미가 문제풀이가 됐으면 좋겠다.
일단 촌수계산은 어릴때부터 많이해봐서 문제 자체는 어렵지 않았다. 그래프를 그릴수만있다면
진짜 한조각 케익이라고 생각했다. 막상 그래프를 그리고 어떻게 돌아야 효율적일까 하는 고민을 하게되었다.
나는 queue를 이용해서 BFS방식을 사용하였다.
촌수를 계산할 두명중 한명을 큐에 넣어주고 그 한사람과 연결된 모든 사람을 큐에 집어넣는다.
그리고 방문했다는 표시를 해준다. 그렇게 그래프를 돌다가 찾는 사람을 발견하면 관계를 출력해주면 된다.
한 계층씩 내려갈때마다 time을 늘려줌으로써 몇 촌인지 계산한다.
싸이월드에서는 너와 나는 1촌이었는데, 지금 우리는 몇촌일까?
삼시세끼 어촌편 보러가야짓,, 쵼쵼!
#include <iostream>
#include <queue>
using namespace std;
struct Que {
int x;
int time;
};
int board[102][102];
bool vis[102];
void initialize() {
for (int i = 0; i < 102; i++) {
vis[i] = false;
for (int j = 0; j < 102; j++) {
board[i][j] = 0;
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int n; //사람 수
int a, b; // 촌수계산 두사람
int m;
int x, y;
int relation = -1;
cin >> n >> a >> b >> m;
initialize();
while (m--) {
cin >> x >> y;
int i = 0;
while (board[x][i] != 0) {
i++;
}
board[x][i] = y;
int j = 0;
while (board[y][j] != 0) {
j++;
}
board[y][j] = x;
} // 그래프 형성
queue<Que> Q;
Q.push({ a,0 });
vis[a] = true;
while (!Q.empty()) {
auto cur = Q.front();
Q.pop();
int i = 0;
while (board[cur.x][i] != 0) {
int neighbor = board[cur.x][i];
if (neighbor == b) {
relation = cur.time + 1;
goto ijsilver;
}
if (vis[neighbor] == false) {
Q.push({ board[cur.x][i],cur.time + 1 });
vis[board[cur.x][i]] = true;
}
i++;
}
}
ijsilver:
cout << relation << endl;
return 0;
}
//양방향 간선을 통해서 그래프를 그리자.
가장 기본에 충실한 문제 같으면서도, 막상 어떻게 노드들의 구현을 해야할지 의문이 많이 들었다.
배열로 board를 만들어야할까 vector로 만들어야할까 고민도 굉장히 많이했다.
DFS를 구현할때는 stack을 쓸까 재귀를 쓸까도 고민을 많이했는데, 스택보다 재귀가 편하다고 판단되어 재귀를 사용하였다. 어짜피 DFS는 한곳 쭉~~~파다가 막히면 돌아오는 개념이기 때문에 재귀가 그 개념과 부합되는 이미지라고 판단했기 때문이다.
BFS는 평소 하던대로 queue를 사용하였다. 방문 여부를 묻고 큐에 넣고 출력을 해주었다.
내 소스코드에서 큐는 하나 선언했다. 코드 제출도 1번만 하였다. 이건 말그대로 당구장 아니지만 원큐였다.
참고하고 댓글로 피드백 주면 감사하겠습니다.
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int board[1002][1002];
bool vis[1002];
void dfs(int v) {
cout << v << " ";
vis[v] = true;
int i = 0;
while (board[v][i]) {
if (vis[board[v][i]] == false) {
dfs(board[v][i]);
}
i++;
}
}
void bfs(int v) {
queue<int> Q;
Q.push(v);
vis[v] = true;
while (!Q.empty()) {
int cur = Q.front();
Q.pop();
cout << cur << " ";
int i = 0;
while (board[cur][i]) {
int node_num = board[cur][i];
if (vis[node_num] == false) {
Q.push(node_num);
vis[node_num] = true;
}
i++;
}
}
}
void board_initialize() {
for (int i = 0; i < 1002; i++) {
for (int j = 0; j < 1002; j++) {
board[i][j] = 0;
}
}
}
void vis_initialize() {
for (int i = 0; i < 1002; i++) {
vis[i] = false;
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int N, M, V;
int a, b;
cin >> N >> M >> V;
//배열 초기화
board_initialize();
vis_initialize();
for (int i = 0; i < M; i++) {
cin >> a >> b;
int j = 0, k = 0;
while (board[a][j]) {
j++;
} // 간선 넣을 곳 찾기
board[a][j] = b;
while (board[b][k]) {
k++;
}
board[b][k] = a;
} // 양방향 노드 간선 추가하기
for (int i = 1; i <= N; i++) {
int j = 0;
while (board[i][j]) {
j++;
}
sort(board[i], board[i]+j);
} // board 오름차순으로 정렬
dfs(V);
cout << endl;
vis_initialize(); // 방문 여부 초기화
bfs(V);
}
이 문제는 11개월 전에 풀었던 문제였다. 그때도 굉장히 어려워했던 문제였는데, 지금도 똑같았다. ㅋㅋㅋㅋ 문자 그대로 ㅁㅊ 소리가 나왔다. 예외처리를 해줄 것이 생각보다 많았기 때문이다.
오랜만에 문제를 푸는 거라 좀 어려움이 있었고, deque를 오랜만에 써봐서 어색했지만 초반 기능 구현은 어느 정도 괜찮았던 것 같다. 그리고 코드가 좀 지저분한데 앞으로 좀 더 개선해 나갈 것이다.
코드 구성은 일단 입력받을 것들 입력받는다. 11개월 전에는 string으로 받지 않고 char 배열로 받았었는데, 배열의 크기까지 고려해야 해서 string을 사용했다. 그리고 문자열로 받은 숫자 배열을 변환하는데 고민을 조금 했는데, 코드 보면 나름 이해할 수 있을 것이다. 처음 '[' 문자는 날려주고 그다음 문자부터 '0'~'9' 사이일 때 숫자로 변화해주는 것을 했다. 처음에는 두 자릿수 세자릿수 고려를 하지 않아 틀렸었는데, 이것까지 고려해서 수정하였다.
그다음은 deque를 이용하여 쉽게 구현하였다.
궁금한 것은 deque를 while문 안에 선언했을 때가 while문 밖에 선언했을 때보다 메모리 활용이 적다는 것이다.
아래는 while문 밖에 선언했을 때이고, 위에는 현재 코드처럼 while문 안에 선언한 것이다.
이유를 안다면 댓글로 달아주면 감사할 것 같다.
#include<iostream>
#include<string>
#include<deque>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T, p;
bool FR, err;
string str, numline; //명령어, 숫자 배열
cin >> T;
int i;
while (T--) {
deque<int> dq;
FR = true;
err = false;
cin >> str >> p >> numline;
i = 1;
while (numline[i]!='\0'){
int x = 0;
while (numline[i] >= '0' and numline[i] <= '9') {
x *= 10;
x += int(numline[i] - '0');
i++;
}
if (x != 0) {
dq.push_back(x);
}
i++;
}
i = 0; //변수 또 할당하기 귀찮고 메모리 아깝다고 판단해서 변수 초기화
while (str[i]!='\0') { //여기서 문자열 판별
if (str[i] == 'R') {
FR = !FR;
}
else if(str[i]=='D') {
if (dq.empty()) { //deque가 비어있을때 D명령어가 나오면 error발생
cout << "error" << endl;
err = true;
break;
}
if (FR) {
dq.pop_front();
}
else {
dq.pop_back();
}
}
i++;
}
//출력하는 부분 error 여부에 따라 '[',']'기호도 출력할지 판단
if (!err) {
cout << "[";
}
while (!dq.empty()) {
if (FR) {
auto c = dq.front();
dq.pop_front();
cout << c;
}
else {
auto c = dq.back();
dq.pop_back();
cout << c;
}
if (!dq.empty()) {
cout << ",";
}
}
if (!err) {
cout << "]"<<endl;
}
}
}
