그래프 (63) 썸네일형 리스트형 나이트의 이동 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #include #include using namespace std; int d[300][300]; int dx[] = {-2,-1,1,2,2,1,-1,-2}; int dy[] = .. 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 배열 받는 문제일 때 행과 열이 맞는지 잘 구분하자!!!! 문제마다 조건이 다르다!! 배열을 받을 때 익은 토마토는 큐에 넣는다!!! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 5.. 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.www.acmicpc.net왜 BFS인가?BFS는 단계별로 진행된다.인접한 정접들을 큐에 넣고 거리가 1다시 인접한 정점들을 큐에 넣고 거리가 2つづく최단 거리를 구할 수 있다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#define _CRT_SECURE_NO_WARNINGS#include cstdio>#include algorithm.. 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net DFS나 BFS를 이용해 연결요소의 개수를 알아내면 끝 인접 행렬과 인접 리스트를 사용할 필요도 없다! 그냥 행렬의 인덱스의 차이를 이용하자! BFS 버전 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49.. 이분 그래프 그래프를 그룹 2개로 나눌 수 있는 그래프를 이분 그래프라고 한다! 이런 식으로 1 -> 4로 가면 4는 2번 그룹 4-> 2 가면 2는 1번 그룹 つづく DFS 탐색으로 이분 그래프인지 판단 할 수 있다. 모든 노드에서 DFS 하는 이유? 그래프의 모든 노드가 안 이어져있을 수도 있으므로. color 배열을 사용하면 visited 배열을 따로 만들지 않아도 된다. https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1 2 3 4 5 6 7 8 9.. DFS와 BFS, 촌수 계산 목적 임의의 정점에서 시작해 연결되어 있는 모든 정점을 1번씩 방문하는 것 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 with Stack(재귀함수) 시간 복잡도 O(V+E) = O(E) BFS with Queue 큐에 넣을 때 check 처리 시간 복잡도 O(E) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28.. 그래프 with C++ https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 알아는 두자 간선 리스트 (Edge List) 링크드 리스트를 쓰기 싫을 때.. 쓰는 방법 일차원 배열에 '모든 간선'을 저장 간선이 들어간 배열을 정렬하고 cnt 배열에서 세어준다. 인접 행렬, 인접 리스트, 간선 리스트를 이용해 이 문제를 풀어보자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 5.. 이전 1 ··· 5 6 7 8 다음
