본문 바로가기

DFS11

10026 : 적록색약 (C++) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 오랜만에 풀어보는 그래프탐색 문제 한 개의 dfs함수를 만들어서 문제를 해결 해 보고 싶었지만 결국 두개로 나누어 만들어 문제를 해결했다. 한개로 합쳐 만들 수 있을까? #include #include #include using namespace std; char map[100][100]; bool visit[100][100]; bool visitColor[100][100]; int N; int colorWeak = 0; int normal = 0; int.. 2021. 2. 12.
1987 : 알파벳 (C++) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백트래킹기법을 사용하여 푼 문제이다. 백트래킹을 사용했기 때문에 visit배열을 따로 사용하지 않았다. #include #include using namespace std; int map[20][20]; bool check[26]; int R, C; int result = 0; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; void dfs(int x, int y, int cnt) { for(int i = .. 2021. 2. 9.
7569 : 토마토 (C++) 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 백준 7576번 : 토마토의 3차원 버전인 문제이다. 3차원 배열을 처음 써봐서 조금 헷갈렸지만 그래도 금방 풀었다! 여러가지 C++에 내장된 함수들을 써보는듯. 다른 글들을 보니 pair이런 방법도 쓴 사람도 있었다. #include #include #include using namespace std; #define MAX 100 int map[MAX][MAX][MAX]; bool visit[MAX][MAX][MAX]; int dx[6].. 2021. 2. 8.
1697 : 숨바꼭질 (C++) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 전에 처음 이 문제를 봤을 때 문제에 어떻게 접근을 해야 할 지 몰라 안풀고 있었는데 오늘 그냥 한번 부딪혀 보자라는 마음으로 문제를 풀어봤다. BFS로 풀어봤다. #include #include using namespace std; int N, K; int map[100001]; bool visit[100001]; int dx[3] = {1, -1, 2}; void bfs(int x) { queue q; visit[x] = true;.. 2021. 2. 8.
2468 : 안전 영역 (C++) 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다. 비의 양이 정수만큼 내리는게 아니므로 아무 지역도 물에 잠기지 않을 수 있다. 값을 다 받으면서 제일 높은 위치 값을 확인 한 후 제일 높은 위치의 값 만큼만 확인해 보면된다. 각각 높이별로 DFS를 실행하여 안전한 영역의 수의 최대 개수를 비교하면서 구한 후 출력하면 끝. 오늘 문제 많이풀었다. #include using namespace std; #define MAX 100 int map[MAX][MA.. 2021. 2. 4.
7576 : 토마토 (C++) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 토마토의 상태는 3가지(익은 토마토 1, 익지 않은 토마토 0, 토마토가 들어있지 않은 칸 -1)로 나타낸다. 토마토가 들어있는 곳이 있다면 바로 큐에 집어 넣는다. 큐에서 하나하나씩 꺼내 근처에 익지 않은 토마토가 있으면 1을 더한다. 반복. #include #include using namespace std; #define MAX 1000 int map[MAX][MAX]; bool visit[MAX][MAX]; queue q; int dx[4.. 2021. 2. 4.
4963 : 섬의 개수 (C++) 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이번 문제는 보통 문제들과는 달리 8방향으로 이동할 수 있다. 보통 상하좌우라면 이 문제는 대각선 방향으로도 갈 수 있어서 4방향으로 더 검사를 진행해야한다. BFS방식으로 문제를 해결하였다. #include #include using namespace std; #define MAX 50 int w, h; int map[MAX][MAX]; bool visit[MAX][MAX]; int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1}; int.. 2021. 2. 4.
1012 : 유기농 배추 (C++) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 테스트 케이스가 여러개 존재 할 수 있으므로 배열 초기화를 반드시 해주어야한다. BFS방식으로 풀었다. #include #include using namespace std; #define MAX 50 int M, N, K; int map[MAX][MAX]; bool visit[MAX][MAX]; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; void bfs(int x, int y) { queue q; q.push({x, y}.. 2021. 2. 4.
1743 : 음식물 피하기 (C++) 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net 먼저 음식물이 떨어진 좌표값들을 입력 받은 후 DFS를 실행한다. #include using namespace std; #define MAX_VALUE 101 int N, M, K; int map[MAX_VALUE][MAX_VALUE]; bool visit[MAX_VALUE][MAX_VALUE]; int cnt = 0; int result = 0; int dx[4] = {1, -1, 0, 0}; int dy[4] = .. 2021. 2. 4.

티스토리툴바