https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 그래프에서 사이클을 찾아내는 문제. DFS로 접근했다. dfs를 진행할때, 바로 전에 지나고 있던 점의 위치를 px, py에 담아놓아서, 탐색한 다음 뒤를 돌아서 다시 탐색하는것을 막아준다. 보통은 방문 여부를 저장하는 vis 배열을 통해서 재탐색을 막아주는데, 방문여부를 통해서 재탐색을 막을 수 없는 이유로 문제에서 요구하고 있는 것이 "방문한 적이 있던 같은 점의 색을 가진 위치" 로..
https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net 그래프 순회 문제입니다. #으로 연결된 묶음들을 한 덩어리로 볼때 덩어리의 갯수를 세서 출력해주는 문제입니다. 입력 방식이 다를 뿐 기본적으로 1012 유기농 배추와 다르지 않습니다. DFS 사용해서 해결했습니다. #include using namespace std; string s[123]; bool vis[123][123] = {0}; int dx[] = {1,-1,0,0}..
변수초기화를생활화하자! 변수초기화를생활화하자! 변수초기화를생활화하자! ㅠㅠㅠㅠ https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 수의 범위가 크지 않아서 DP배열을 선언하기 그리 어렵지 않다. DP배열을 선언해두고 dfs나 bfs 등의 방법으로 가능한 가짓수 여섯가지 경우에 대해 탐색을 해주면 되는데, 탐색 중간에 SCV의 체력이 음수로 내려가는경우 음수 인덱스에 접근하게 되면서 세그폴트가 발생할 수 있으므로, k = max(k,0) 등의 구문을 통해서 ..
www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 처음 보고 든 생각은 "R과 C의 범위가 작으니까 DFS등으로도 해결할 수 있을 거 같다" 였다. 구현 방법은 뭐 여러가지가 있겠지만, 나는 비트마스킹을 연습할 겸 비트마스킹으로 해결해 보기로 했다. 우선 들어오는 문자들에서 'A'만큼을 빼서 0부터 시작하는 숫자로 만들어준다음 각각 0 번째 비트, 1번째 비트, .... 등으로 각각의 비트에 방문여부를 기록해준다. 더보기 #include using na..
제목이 같은 날먹문제... 트리에 존재하는 모든 경로 중 가장 긴것의 길이를 찾으라하고 있다. dfs로 풀었다. 일단 가장 긴 경로는 반드시 리프노드 - 리프노드 간 길이일 것이다. 리프노드가 아닌 노드가 긴 경로가 된다면 그 노드의 자식노드로 더 긴 경로가 있을수밖에 없기 때문이다 ( 가중치의 길이가 음수가 될 수 없다 ) 처음 생각한것은 1을 기준으로 가장 긴 경로 & 두번째로 긴 경로 를 찾는 것인데, 중복문제도 있고, 그림에서처럼 1을 지나지 않는 가장 긴 경로도 있기에 일단 루트노드에서 가장 긴 경로를 찾고, 그 경로에서 나온 리프노드를 시작점으로하는 가장 긴 경로를 찾아주었다. 루트노드에서 가장 긴 경로와 실제 가장 긴 경로가 1 ) 하나도 겹치지 않는다면 조건에 모순이 생기고, 2 ) 겹친다..
간단한 dfs문제 1번부터 순회하면서 출력해주면 반드시 사전순을 충족하게 짤 수 있다. www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net arr[]은 출력할 답을 저장하는 배열이고, visit[]은 방문여부를 저장해준다. ( 같은 수가 중복으로 나오는것을 방지하기 위해서 ) #include #include using namespace std; int n,m; int arr[10] = {0}; int visit[10] = {0}; void dfs(int k){..