coding tasty house

문제 https://www.acmicpc.net/problem/1987코드# 백트래킹 문제 import sysfrom collections import dequesys.setrecursionlimit(10**9)def Input_Data(): input = sys.stdin.readline R, C = map(int, input().split()) graph = [] for _ in range(R): graph.append(list(input())) return R,C, graphd = ((1,0),(-1,0),(0,1),(0,-1))def Dfs(x,y,cnt): global ans ans = max(cnt, ans) for dx, dy in d..

문제https://www.acmicpc.net/problem/13023 코드 import sysfrom collections import dequesys.setrecursionlimit(10**9)def Input_Data(): input = sys.stdin.readline N, M = map(int, input().strip().split()) adj = {i : [] for i in range(N)} for _ in range(M): a, b = map(int, input().strip().split()) adj[a].append(b) adj[b].append(a) return N, M, adjdef Dfs(start, depth): ..

문제 https://www.acmicpc.net/problem/1068 코드import sysfrom collections import dequesys.setrecursionlimit(10**9)def Input_Data(): input = sys.stdin.readline N = int(input()) node = list(map(int, input().split())) erase = int(input()) #지울 노드 adj = [ [] * (1) for _ in range(N)] # 간선 저장 for idx, v in enumerate(node): if v == -1 : # root root = idx elif id..

문제설명 https://www.acmicpc.net/problem/2468 알고리즘 1. 그래프 입력(최대높이 저장) 2. 높이별로 반복해서 dfs 연산 3. 최대 높이 출력 코드 #include #include #include using namespace std; int graph [101][101]={0,}; bool visited[101][101]={0,}; int dx[4] ={1,-1,0,0}; int dy[4] ={0,0,1,-1}; int N; void dfs(int x, int y, int height){ visited[x][y]= true; for (int i = 0; i = N || dx[i]+x =N || dy[i]..

문제설명 알고리즘 1. 입력 받기 : 그래프 크기, 현재 위치, 방향, 그래프 형태 2. 방향 설계 -> 북 서 남 동 순으로 회전하기 때문에 dx,dy에 전진할때 발생하는 값을 정의해 둔다 3. 왼쪽으로 돌고, 안갔으면 간다. 단 갔으면 왼쪽으로 돈다 4. 4방향 다 돌았는데 갈 수 있는 곳이 없는 경우 그 자리에서 1칸 후진한다 5. 후진하려는데 그 뒤도 막혔으면 종료 코드 1) 시행착오 #include using namespace std; //탐색 int dx[4] = { 0,-1,0,1 }; //d=0 ~ 3일때 x의 이동 값 int dy[4] = {-1,0,1,0 }; //d=0 ~ 3일때 y의 이동 값 //후진 int bx[4] = { 1,0,-1,0 }; //d=0 ~ 3일때 x의 이동 값 ..

문제설명 알고리즘 1. 가로 세로 및 그림의 정보 입력 및 저장 2. dfs 알고리즘을 사용하되, 가로세로 연속된 그림의 넓이와 수를 구함 3. 출력 코드 #include #include #include using namespace std; #define MAX 505 int graph[MAX][MAX]; int visited[MAX][MAX]; int max_width, N,M,width; void dfs(int x,int y) { visited[x][y] = true; //방문 width++; //가로 세로 넓이 구함, 단 범위 판단 필수 if (graph[x + 1][y] == 1 && visited[x + 1][y] == 0 && (x+1 < N)) { dfs(x + 1, y); } if (gra..

문제설명 이 문제는 연결관계를 파악하여 해킹 가능한 컴퓨터가 많은 컴퓨터를 출력한다 만약 그 갯수가 동일하다면, 컴퓨터의 번호를 오름차순으로 출력한다 알고리즘 1. 컴퓨터의 수와 간선의 관계를 입력받는다 2. 간선의 관계는 단방향으로 저장한다(b가 해킹되면 a도 가능하다) 3. bfs 함수에서 각 컴퓨터가 해킹가능한 컴퓨터의 수를 센다 4. 컴퓨터의 수와 컴퓨터 번호를 저장한다 5. 정렬을 통해 해킹 할 수 있는 컴퓨터의 수가 가장 많은것, 그리고 인덱스는 오름차순으로 정렬한다 6. 첫 값은 무조건 가장 크기때문에 이와 같은 값인 컴퓨터의 인덱스를 모두 출력한다 코드 #include #include #include #include using namespace std; vector graph[10001];..

문제설명 해당 문제는 그래프에서 이동 수를 구하는 문제이다 시작 노드에서 도착 노드까지 도달하는데 이동 수를 구하면된다 먼저 총 가족의 수와 구하고자 하는 노드, 연결관계를 입력받는다 촌수 == 도달 하기위해 거쳐가야 하는 노드의 수 라고 생각하고 풀면된다 알고리즘 1. 필요한 정보(가족 수, 구하고자 하는 관계, 관계 정보)를 입력 받는다 2. 현재 노드에 방문 표시를 한다 3. 현재 노드와 연결된 노드를 조회하여 방문 하지 않은 경우 방문한다. 단 방문시 이동 값을 올려준다 4. 노드가 도착점에 닿았을 때 현재 이동한 수를 저장해둔다 5. 함수를 빠져나오면 저장해둔 이동 수를 출력시킨다 6. 만약 출발점에서 도착점에서 도달하지 못한 경우 -1을 출력시킨다 코드- (1) ->DFS #include #i..

문제설명 땅과 바다의 값을 입력 받은 다음 총 섬의 개수를 구하는 문제이다. 여러번 테스트 케이스를 입력 받을 수 있도록 코드를 짜야하며, 지도의 너비와 높이가 주어진다. 1은 땅, 0은 바다로 간주한다. 이때 땅은 가로, 세로 뿐만 아니라 대각선으로도 갈 수 있다. 알고리즘 1. 지도의 너비와 높이를 입력받는다 2. 지도의 정보(0과 1)을 입력받는다 3. 상하좌우, 대각선 연결된 섬을 찾는다(dfs 알고리즘 사용) 4. 섬의 개수를 센다 5. 지도를 초기화 한다. 코드 #include #include #include #include using namespace std; #define MAX 51 int graph[MAX][MAX]; bool visited[MAX][MAX]; void dfs(int x..

연결 요소의 갯수 문제설명 첫 줄에 노드의 수 , 간선의 수를 입력 받는다. 총 연결된 요소의 갯수를 출력한다. 알고리즘 노드의 수와 간선의 수를 입력 받는다. 연결 여부를 나타낼 graph인 2차배열, 방문여부를 나타낼 배열을 N+1크기만큼 만든다. 간선의 연결 관계를 입력 받고, (2,1)인경우 (1,2)에도 값을 넣는다. 반복적으로 조회하여 방문하지 않은 경우 (False인 경우) dfs 함수에서 동작한다. 연결의 수를 출력시킨다. import sys sys.setrecursionlimit(10000) # 깊이 우선 탐색 def DFS(v): visited[v]=True for e in graph[v]: if not visited[e]: DFS(e) N, M = map(int, sys.stdin.r..