본문 바로가기
백준온라인저지(BOJ)/#2583/DFS/영역구하기 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net 영역 구하기 문제다. 마찬가지로 2차원 좌표에서의 DFS탐색을 필요로 한다. 모눈종이에 그려진 직사각형의 영역만큼 마킹을 한 뒤(board[][]++..
백준온라인저지(BOJ)/#2667/단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 단지별로 house_count를 도입하여, DFS가 재귀적으로 호출될 때마다 Call Stack에 쌓일때마다 house_cnt++로 풀면 될 것이다. 이렇게 한 세..
백준온라인저지(BOJ)/#1012/유기농 배추 유기농 배추 문제이다. 문제에서 밭이 있으면, 1로 칠해진 밭끼리 끊어지지 않고 연결된 연결 고리(?) 집합이 몇 개 인지 구하면 된다. dfs로 풀 수 있는데, 다만 동서남북 좌표로 dfs를 탐색한다고 보면 된다. 주황색으로 동그라미 친 포인트를 시작점이라고 할 때 동서남북, 4번 반복하면서 시작포인트와 인접한 포인트가 1인 지점을 발견한다면, 거기로 포인트를 옮기고, 옮긴 포인트를 Argument(인자)로 dfs를 재귀 호출해준다. #include #include using namespace std; vector board; int M, N, K, x, y; const int dy[] = {0, 0, -1, 1}; const int dx[] = {-1, 1, 0, 0}; void dfs(int y, ..
BOJ(백준온라인저지)/11724/연결 요소의 개수 문제: https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. www.acmicpc.net 그래프 자료형인 인접 리스트가 주어질 때 연결 요소의 개수를 묻는 문제이다. DFS를 이용하면, 쉽게 풀 수 있는 문제다. 문제 풀이 설계는, 1. 먼저 cin으로 adj list를 입력받기(adjacency list는 시작 - 끝, 끝 -시작 양 방향으로 우선 받아야 하므로 adj[u].push_back(v); adj[..
BOJ(백준온라인저지)/1260/DFS와 BFS 문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net DFS/ BFS의 기본 문제다. 탐색 순서를 그대로 출력하여, DFS와 BFS가 각각 구동하는 방식을 볼 수 있다. 시작점을 parameter 로 잡고, DFS, BFS function을 Void( Return 값 없음)형으로 구현하였다. 주의해야할 포인트가 몇 가지 있다. 1..
DFS 기본 개념 및 구현 코드 DFS이다. 너비가 아니고 깊이를 우선으로 탐색하는 것을 의미한다. 위 사진의 동작을 보면 알 수 있음 여기서 깊이라는 것은 시작 노드로부터 떨어진 거리라고 볼 수 있겠다. 이를 좀 더 구체적으로 표현하면(컴퓨터의 사고방식으로 표현하면), 1. 어떤 탐색 시작 노드에서 시작하여, 간선으로 연결된 노드가 아직 방문되지 않은 노드라면 2. 무조건 그 간선을 먼저 따라가는 방식으로 구동되는 것이다.(이 때 재귀적인 방식이 이용된다.) 코드로 구현하면,(C++)아래와 같습니다 #include #include using namespace std; vector adj; // Set Adjacency List vector visited; //dfs (node) 의 구현 parameter를 here이라는 탐색하고자 하..
프로그래머스 신기능_ 스킬체크 기능 우선 레벨1은 패스.. 레벨 3정도까지 우선 따두는 것이 목표다. 과연 내가 지원할 기업에서 내가 셀프로 따 놓은 스킬테스트를 참조할까?? 어쨌든 조금이나마 유저의 문제 풀이 능력을 기업에 어필할 수 있으니 나쁠건 없는 기능같다.
BFS 기본 개념 및 구현 코드 자, 이것이 BFS다. 한글로는 너비 우선 탐색이라고 한다. 그림은 쉽다. 움직이는 그림에서 보면 제일 위에 있는 Node부터 탐색을 시작해서, 제일 위의 노드와 직접 연결된 두 번째 노드 (3개)를 탐색하고, 아래도 이와 같은 방식으로 탐색하는 것이다. 이 탐색을 하는 것이 마치 넓게 인접 노드부터 차례로 탐색하는 모양새므로 너비를 우선으로 탐색한다 -> BFS, '너비 우선'탐색이라 하는것이다. 저 구슬 알갱이들을 node라 부르고, 그 Node들은 간선(Edge)로 이어져있다. '그래프'(Graph) 자료구조를 이용하여 구현해야하는 알고리즘이니 BFS를 보기 전에 그래프라는 자료구조 개념을 먼저 알고 오는 것이 좋다. 자, 각설하고 구현을 해보자. 그림은 단순하지만 구현은 노드를 바로 탐색(or 방..

티스토리툴바