노는 게 제일 좋아

DFS + DP 문제다. DFS를 어떻게 설계해야할까? 가 문제다. https://www.acmicpc.net/problem/1937 #맞는 풀이 #include #include #define X first #define Y second using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int map[500][500]; int dp[500][500]; int N; int ans; //좌표 int dfs(int x, int y) { //만약 저장되어있지 않으면 if(dp[x][y] == 0){ dp[x][y] = 1; // 우선 해당 노드에서 1일 살 수 있음( + 방문체크와 같음) int cnt = 0; // 몇개나 다른 노..

비트는 아주 유용하다. 이 문제를 풀 때 차원을 어떻게 표현하지? 라고 생각했지만 누군가가 비트라고 속삭여서 풀 수 있었다. [문제풀이(Problem Solving)] - 백준, BOJ, 1194번, 달이 차오른다 가자 4 : C++ [CPP] ****** 이러한 비트에 대해 알아보도록 하자. 우선 bitset이라는 STL부터 알아보자 A bitset stores bits (elements with only two possible values: 0 or 1, true or false, ...) 0, 1의 값을 보통 가진다. **false, true 로도 사용함. 비트셋(Bitset) 함수들 bitset 이름; bitset 선언 bit.set() 모든 비트 1로 초기화 bit.reset() 모든 비트 0으..

할 말이 아주 많다. 어려웠다. 처음에 6가지 상태를 어떻게 표현하지.. 하다 차원이 무지막지하게 늘어나길래.. 이게 아닌가?? 하다가... 비트라는 힌트를 얻어서 풀었다. 잠잘 때도 어떻게 풀지 하다가.. 비트라는 힌트만 보고 머릿속으로 생각하고 오늘 바로 풀었다. 기분이 좋다. https://www.acmicpc.net/problem/1194 #맞는 풀이 #include #include #include #include #include //bit 연산을 위함 #define SIZE 50 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; //key를 비트로 표현하자. 000000 -> 6비트로 표현가능 6가지 상태 저장가능 ..

1000* 1000의 탐색은 쉽게 시간초과가 된다는 것을 충분히 인지해야 한다. 그래서 어려웠다. 1000* 1000 사이즈의 노드에서 하나씩 BFS하는 것은 (1000 * 1000) 에 대해 (1000*1000) 을 수행하는 것과 같다. 즉, 시간초과다. https://www.acmicpc.net/problem/16946 #맞는 풀이 #include #include #include #include #include #define X first #define Y second #define SIZE 1000 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int r, c; //행, 열 char given[SIZE][SIZE];..

벽을 부수다가 기다릴 줄도 알아야한다는 것이 조금 까다롭다. https://www.acmicpc.net/problem/16933 #맞는 풀이 #include #include #include #define X first #define Y second #define SIZE 1000 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; char arr[SIZE][SIZE]; //입력 int visited[SIZE][SIZE][11]; // 0 벽을 안깼다, 1 개깼다 .. 10개 깼다. int r, c, crush; typedef struct Position { int x; int y; int wall; int waiting; //..

벽을 여러개 부술 때이다. 1을 풀었다면 어떻게 해야할 지 알것이지만 벽만 바꾸는 것이 아니라 방문 조건도 바뀐다. 밑에서 조금 더 설명해보자 https://www.acmicpc.net/problem/14442 #맞는 풀이 #include #include #include #define X first #define Y second #define SIZE 1000 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; char arr[SIZE][SIZE]; //입력 int visited[SIZE][SIZE][11]; // 0 벽을 안깼다, 1 개깼다 .. 10개 깼다. int r, c, crush; typedef struct Posi..

어려웠다. 개념이 아주 새로웠다. 복습 다시 천천히 해보자 https://www.acmicpc.net/problem/2206 #맞는 풀이 #include #include #include #define X first #define Y second #define SIZE 1000 using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; char arr[SIZE][SIZE]; //입력 int visited[SIZE][SIZE][2]; // 0 벽을 안깼다, 1 깼다 int r, c; typedef struct Position{ int x; int y; int wall; }Pos; int BFS(int _x, int _y) { queue ..

어려웠다. 조건이 많았기 때문이다. https://www.acmicpc.net/problem/2573 #맞는 풀이 #include #include #define X first #define Y second using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int R, C; int curMap[300][300]; int nextMap[300][300]; int year = 0; int visited[300][300]; //dfs를 위함 void melting(int x, int y) { int cnt = 0; //주변 바다의 칸 for (int dir = 0; dir < 4; dir++) { int nx = x + dx[dir..

이 문제 어렵다기 보다. 조건이 진짜 많아서 내 몸에 해롭다. https://www.acmicpc.net/problem/3055 #맞는 풀이 #include #include #include #include #include #define X first #define Y second using namespace std; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int water[50][50]; // 물이 가는길 int man[50][50]; // 사람이 가는 길 int R, C; int main() { cin >> R >> C; int sx, sy; //시작위치 int ax, ay; //도착해야하는 위치 //man, water -1로 초기화. for (in..

어렵지 않았지만 입력이 귀찮았다. https://www.acmicpc.net/problem/10026 #맞는 풀이 #include #include #include #define X first #define Y second #define SIZE 100 using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int rg[SIZE][SIZE]; //적녹 색약 visit int norm[SIZE][SIZE]; // 보통 visit int n; // 행,열 int normCnt, rgCnt; // 답 string arr[SIZE]; //입력 int main(){ cin >> n; //노드입력 for(int i = 0; i> arr[i]; } q..