With The Lights Out

[C++ / 백준 7576번] 토마토

문제  시행 착오 두 개 이상의 토마토가 0일차에 들어 있을 때, 두 번 이상의 bfs 를 한 번에 하는 방법을 잠깐 고민했었다. 해결 방법 bfs 를 시작하기 전에 배열을 순회해 0일차 토마토의 좌표를 큐에 넣어놓고 bfs 를 시작했다. #define _CRT_SECURE_NO_WARNINGS#include #include using namespace std;/** 익은 토마토의 영향을 받아야 익는다.* 토마토가 없는 칸도 있을 수 있다.* */int tomato[1000][1000];int arr[1000][1000];bool visited[1000][1000];int M, N;int cnt = 0;queue> q;queue> q2;int dy[4] = { 1,0,-1,0 };int dx[4] = {..

문제  시행 착오DFS 로 풀이하려다 시간 초과가 났다. 잘 생각해보니 DFS보단 BFS 가 훨씬 효율적이고 정확한 듯 해서 바꾸어서 풀었다.  해결 방법  #define _CRT_SECURE_NO_WARNINGS#include #include using namespace std;int N, M;int arr[100][100];int num[100][100];bool visited[100][100] = {false};queue > q;int x_dir[4] = { -1 , 1 , 0 , 0 };int y_dir[4] = { 0 , 0 , -1 , 1 };void bfs(int y, int x){ visited[y][x] = true; q.push(make_pair(y, x)); num[y][x]++; ..

문제 시행 착오 fill 2차원 배열 초기화에 관해 이슈가 있었다. fill 의 두 번째 파라미터는 끝 주소를 포함하지 않기 때문에 끝 주소 + 1 을 해 주어야 올바르게 초기화가 되었다. 해결 방법 DFS를 이용해 범위 내에서 문제 조건에 따라 순회 해 주었다. DFS 가 끝날 때마다 cnt+1 을 시행했다.재방문은 그대로 리턴하도록 하였다. #include using namespace std;bool visited[50][50] = { false };int map[50][50]; int cnt = 0;int w, h;void dfs(int y, int x){ if (visited[y][x]) return; if (y = h || x = w) return; visited[y][x] = true; if ..

문제  시행 착오없음  해결 방법순회하며 1을 찾고, 1을 찾은 위치에서 DFS 를 이용해 상하, 좌우에 1이 없을 때까지 탐색했다. 아래는 문제풀이 전에 직접  VS 에 작성한 방법이다.DP 를 풀듯 차근차근 생각하는 것이 도움이 많이 되는 것 같다.생각해 본 해결방법  1. 상하, 좌우 이렇게 두 경우만 집이 붙어있는 경우이다.2. DFS / BFS 중 어느거라도 사용한다.3. 몇 개가 붙어있는지 세고 오름차순으로 출력한다.  #define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std;vector v;int N;int map[26][26];bool visited[26][26] = { false };int cnt = 0;v..

문제   시행 착오인접 정점을 어떻게 해야 번갈아 가며 색으로 칠할 수 있는 지 고민했다.   해결 방법삼항연산자로 간편하게 인접 정점에 부모 노드와 다른 색을 칠할 수 있었다.. 예시 :void DFS(int node, int c) { color[node] = c; visited[node] = true; for (auto v : g[node]) { if (color[v] == 0) { // 방문 안 한 경우 DFS(v, c == RED ? BLUE : RED); } }}     DFS 사용해서 해결#include #include #include #include #define RED 1#define BLUE 2using namespace ..

문제 시행 착오 연결 요소  연결 요소란 간단히 말해서 간선으로 이어진 정점들의 한 뭉탱이를 말한다.1-3-5   2-4 이렇게 연결 된 정점들이 있다면 연결 요소는 두 개인 것.   해결 방법 dfs 혹은 bfs 를 시행했을 때 한 번의 시행으로 전부 순회가 안 된다면 연결 요소가 두개 이상 있는 것이다. 두해당 알고리즘 시행 횟수만큼이 연결 요소의 개수가 된다. #include #include #include #include using namespace std;int N, M, V;vector g[1001];bool visited[1001] = { false };queue q;int cnt = 0;void dfs(int node){ visited[node] = true; for (a..

문제  시행 착오  해결 방법 벡터를 이용해 그래프를 구현하고, DFS 는 재귀호출을 통해, BFS 는 큐를 이용해 구현했다.정점 순서대로 순회 하려면 입력 받은 뒤 sort를 해주어야 한다.   #include #include #include #include using namespace std;int N, M, V;vector g[1001];bool visited[10001] = { false };queue q;vector v_bfs;vector v_dfs;void dfs(int node) { visited[node] = true; v_dfs.push_back(node); for (int nextnode : g[node]) { if (!visited[nextnode]..

문제   시행 착오  그래프가 기억이 안 나서 복습했다.백트래킹, dfs 는 잘 하지만 그래프와 합쳐지니 연상이 잘 안 되었다. 항상 천천히 알고리즘을 생각해내는 연습이 필요해 보인다. (무작정 아는 방식으로 구현 X 머릿속에서 구체화) 해결 방법 그래프를 선언하고, 각 그래프마다 관계 또한 최대 2000개까지 들어올 수 있다.사실상 2차원 배열 형태를 벡터를 이용해 표현한 것과 비슷한데,  시작 노드를 정한다.시작 노드에 저장되어있는 관계로 접근한다.노드의 관계를 깊이우선탐색 하면서 cnt 가 4가 되는 노드순서를 찾는다.끝   #include #include #include using namespace std;int N, M;vector g[2000];bool visited[2000] = { fals..

문제    시행 착오 비트마스크 알고리즘을 사용해 문제 풀이가 아직 익숙치 않아 풀이가 오래 걸렸다.무에서 유를 창조할 수는 없기에 gpt에게 아이디어만 제공받아 풀이를 시작했다.  해결 방법 문제에서의 힌트는 수는 무조건 행렬에서 각각 성분의 크기가 커지는 방향으로 진행된다는 점이다.따라서 수는 오른쪽, 혹은 아래쪽 으로만 진행하게 된다. 경우의 수가 2개라는 것은 결국 이진으로 표현이 가능함을 알 수 있었다. 배열 3개를 사용했다.입력받은 수를 저장할 arr비트마스크를 통한 경우의수를 저장할 binaryarr방문 여부를 나타내는 visited 방문되어있지 않은 이진배열 위치에서 해당 위치의 값이 아닌 값 (연속되지 않을 때까지, 방문 되지 않은 곳으로) 까지 순회하면서 수를 만들고 더해준 다음 최댓값..

문제   시행 착오 비트마스크 사용법을 몰라 인터넷에 검색해 이해했다. 비트 연산을 통해 백트래킹 사용을 하거나 큰 크기의 배열을 선언할 필요 없이 간편하게 해결할 수 있었다. 비트마스크는 아래 글을 읽고 이해했다. https://velog.io/@alkwen0996/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%AC 컴퓨터는 내부적으로 모든 자료를 이진수(비트)로 처리한다. 이런 컴퓨터의 연산방식을 이용한, 정수의 이진수 표현을 활용하여 문제를 해결하는 기법을 말한다. 비트(Bit)란? 비" data-og-host="velog.io" data-og-source-url="https://velog.io/@alk..