With The Lights Out

문제  해결 방법문제를 해결하기 전에 해결 방법을 생각해 적어보았다.사이클 판단 조건 : 사이클은 무조건 4개로 시작한다. 정사각형부터 직사각형까지 여러 형태이다. 하지만 사이클이 있다면 사이클이 크던 작던 시계방향, 반시계방향 둘 중 하나로 무조건 진행 할 수 있으므로 이를 이용해 DFS 로 탐색 시 원래 정점으로 돌아온다면 사이클 이 있는 것이다.  사이클이 있을 시 정점의 개수가 4 이상이어야 하지만 내가 짠 코드에서는 논리 구조상무조건 원래 위치로 돌아왔을 때(그러려면 자연스레 정점을 4개 를 밟는다) 출력을 해주기 때문에 크게 상관없을 듯 하다. 위와 같은 로직으로 (0, 0) ~ (N, M) 까지 bfs 로 전부 순회하며 사이클을 찾았다. #define _CRT_SECURE_NO_WARNING..

문제  시행 착오 두 개 이상의 토마토가 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 ..

구조체 하나의 데이터 타입이 아니라, 다양한 데이터타입을 묶어서 새로운 데이터타입을 필요로 할 때 사용된다. struct Player{    string name;    float moveSpeed;    double attackVaule;    int hp;    bool isDead;    name, moveSpeed, attackValue, hp, isDead}; C++ 에서 구조체와 클래스의 차이점은  구조체는 접근 지정자가 public: 클래스는 private: 이다. 위 사항 말고는 큰 차이점이 없다. 함수 코드를 특정 기능 단위로 묶어 놓은 것. 함수의 유용성1) 코드 자체가 매우 간략해질 수 있다.2) 함수명, 매개변수명=기능을 나타내기 때문에 코드 가독성 / 유지 보수가 편해진다.3) 코..

문제 시행 착오 연결 요소  연결 요소란 간단히 말해서 간선으로 이어진 정점들의 한 뭉탱이를 말한다.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]..

#include #include using namespace std;int main(){ srand(time(NULL)); int escape_x = rand() % (9 - 0 + 1) + 0; int escape_y = rand() % (9 - 0 + 1) + 0; bool escaped = false; char m[10][10]; for (int i = 0; i > input; switch (input) { case 'w': m[curY][curX] = '#'; curY -= 1; m[curY][curX] = 'O'; break; case 'a': m[curY][curX] = '#'; curX -= 1; m[curY][curX] = 'O'; break; ..