jmmm_25

2468번 안전 영역 문제는 BFS 또는 DFS로 해결되는 문제이다.나는 DFS를 공부하고 있으므로 DFS로 풀었다. 여기서 입력 조건에서 높이는 1 이상 100 이하의 정수이다. 라는 말이 있다. 그래서 높이 h를 1부터 시작하게끔 for 문을 돌렸는데,비가 안오는 경우도 있기 때문에 높이가 0일 때도 체크를 해주어야 한다.그래서 처음에 틀렸었다. 80% 다 되가서 틀렸길래 고민을 하다가, 질문을 검색하여 해결할 수 있었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #define MAX_HEIGHT 100..

DFS로 해결가능한 문제이다.인접행렬로 모든 정점을 DFS 탐색하는 것은 처음이여서 많은 시행착오가 있었다.다음부터는 정점 DFS일 때에는 인접 리스트로 푸는 것이 나을 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include using namespace std; int N;int map[101][101];bool isVisited[101][101];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int flag = 0; void dfs(int ret_x, int ret_y, int sta..

적록색약이 아닌 사람이 봤을 때의 구역의 갯수는 일반적으로 알고 있는 DFS 탐색을 하여 구하면 된다. 적록색약일 경우의 구역의 갯수는 R과 G를 동일한 색상으로 파악해야하기 때문에 DFS 탐색 전에 데이터를 약간 변형시켜주었다. 나 같은 경우에는 이중 for문으로 map의 'G'를 'R'로 변경해주어 DFS 탐색을 하였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include #include using namespace std; int N;char map[101][101];bool isVisite..

이 문제 같은 경우에는 DFS 또는 BFS로 쉽게 풀리는 문제지만, 좌표를 이상하게 줘서 고생좀 한 문제이다.2차원 배열에 직사각형을 잘 넣을 수만 있다면 DFS의 횟수와 Component의 갯수를 출력하면 되는 문제이기에 단순하다. 2차원 배열에 직사각형을 넣지를 못해서 구글링을 했다.단순하게 생각하면 배열에 집어넣는 것도 간단한 것 같다.좌표가 이렇게 주어지고 map을 만들어본 적이 없어서 당황했지만, 이런 스킬도 알아놓으면 편할 것 같다. for (int i=0; i> x1 >> y1 >> x2 >> y2; for (int x = y2-1; x>=y1; x--) { for (int y = x2-1; y>=x1; y--) { map[x][y] = 1; } } } 이 외에 나머지는 지금까지 풀었던 문제..

2331번 반복수열 문제는 1차원적으로 단순하게 풀었다.N을 입력받고 일의 자리부터 각각 P 제곱을 하여 더하게끔 하고, 나온 결과 값을 벡터에 저장시켰다.그리고 마지막에 중복되는 값이 나오게 된다면, 벡터에 저장되어 있는 값들을 중복된 값 이전까지의 갯수를 출력하면 문제를 해결할 수 있다. 문제의 조건에서 1 > P; v.push_back(N); while (!isCheck[N]) { int ret = 0; isCheck[N] = true; for (int i=N; i>0; i/=10) { ret += pow(i % 10, P); } v.push_back(ret); N = ret; } for (int i=0; i

2667번 단지 번호 붙이기 문제는 DFS를 통해 완전 탐색으로 해결할 수 있는 문제이다.출력에 2가지가 출력이 되어야한다. 1. 연결 요소의 갯수2. 인접한 집의 갯수 2번에서 인접한 집의 갯수를 출력할 때, 오름차순으로 출력을 하라는 조건이 중요하다.이 조건을 깜박하고 제출하였더니 틀렸다고 나와 고생좀 했다. 앞에서 푼 문제들과 비슷한 유형이기에 쉽게 풀 수 있었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include using namespace std; int N, component;int dx[4] =..

1743번 음식물 피하기 문제는 DFS 알고리즘을 통해 인접한 가장 큰 음식물의 크기를 찾으면 된다.dfs를 이용하여 재귀 함수를 호출할 때 마다 cnt를 +1 해주면 된다. 이 문제같은 경우에는 (2,2) 좌표에서 DFS를 호출하여 상하좌우를 다 들어가본 후, 결과 값인 4를 리턴한다. # : TRASH , : EMPTY # . . . . # # . # # . . 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #define TRASH 1#define EMPTY 0#define MIN_INF (-98776321) using namespace std;int N, M, K;int map[10..

이 문제는 전에 풀었던 1012번 문제의 기본 개념이라고 보면 될 것 같다.말 그대로 연결 요소의 갯수를 구하면 되는 문제이다.DFS의 기본 개념만 알면 풀 수 있는 간단한 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include using namespace std; vector adj(1001);vector isVisited(1001);int N, M, ret; void dfs(int v) { isVisited[v] = true; for (int i=0; i N >> M; for (int i=0; i> u >> v; adj[u].push_b..

1012번 유기농 배추 문제는 배추 밭에 배추가 심어져 있는 모든 곳을 다 DFS로 탐색함으로써 답을 찾아낼 수 있다.dfs는 모든 노드들이 연결되어 있는 경우도 있지만, 그렇지 않은 경우도 있다.위의 문제 같은 경우에는 후자이다. 그래프 용어 중에 Component가 있다. Component 하나 안에 속한 정점들은 서로 모두 이어져 있으며, 다른 Component끼리는 이어져 있지 않다.따라서, 배추 밭의 Component의 갯수를 찾으면 된다. map[i][j] == true 인 곳이 배추가 심어져있는 곳이므로, 이 경우에만 dfs 탐색을 시작한다.dx, dy 배열을 이용하여 dfs 탐색을 시작한 해당 위치의 상하좌우를 돌아보며 재귀형식으로 dfs를 탐색한다.한 구역의 dfs 탐색이 끝났으면, 결과..

이 문제는 단순한 DFS와 BFS 구현이다.각 자료구조에 대한 개념만 알고 있다면 충분히 풀 수 있는 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include #include #define TRUE 1#define FALSE 0 using namespace std;int N, M, V;int graph[1001][1001];int isVisited[1001];queue q; void bfs(int V) { int u = 0; q.push(V); isVisited[V] = TRUE; wh..