노는 게 제일 좋아

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; // 몇개나 다른 노..

할 말이 아주 많다. 어려웠다. 처음에 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/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..

음 백트래킹하면서 DFS로 끝까지 가는 것이라 처음 접했을 때는 어려웠다. https://www.acmicpc.net/problem/1987 #맞는 풀이 ( 백트래킹 + DFS ) #include #include #include #include using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; char arr[20][20]; int alpha[26]; // ASCII 코드 이용하기 'A' = 65 'a'=97 int R,C; //Row(행) , Column(열) int answer = 0; // 최댓값 //현재 위치, 현재까지의 길이 void dfs(int x, int y, int dist){ // 최댓값 갱신 answer = ma..

음.. 생각은 빨리했는데.. 오래걸림.. 왜냐면.. 초기화를 잘못했다. 아...내 1시간반 https://www.acmicpc.net/problem/14502 그렇게 어렵지 않았다. 벽을 무작위로 세워야 하는 것을 이미 알기에.. Brute Force를 해야하는 것은 알았지만 그냥 백트래킹 복습삼아 적용했다. 가장 처음 제출한 풀이.. #include #include #include #define X first #define Y second using namespace std; int map[8][8]; int visited[8][8]; int dx[4] = {1,-1,0,0}; int dy[4] = {0,0,1,-1}; int N,M; int ans = 64; stack stk; // DFS 스택 ve..