반응형 dfs8 [BOJ][Python]17070 풀이 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net import sys; ssr = sys.stdin.readline def f(cur_r, cur_c, cur_dir): global ans if cur_r == n-1 and cur_c == n-1: ans += 1 return else: if cur_dir == 0 or cur_dir == 1: if cur_c+1 < n and board[cur_r][cur_c+1] !.. 2023. 10. 30. [BOJ][Python]1987 풀이 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net import sys ssr = sys.stdin.readline def dfs_stack(): global ans s = [(0, 0, board[0][0])] while s: r, c, path = s.pop() if len(path) > ans: ans = len(path) if len(path) == 26: break for dr, dc, in dpos: if 0 2023. 8. 21. [Algorithm][Python]깊이/너비 우선 탐색 알고리즘(DFS/BFS) + 코드 너무 중요한 알고리즘이죠. 대표적인 그래프 탐색 알고리즘인 깊이 우선 탐색, 너비 우선 탐색에 대해서 알아봅시다. 이 그래프를 기본으로 해서 알아보겠습니다. 깊이 우선 탐색(Depth First Search) 먼저 알아볼 것은 깊이 우선 탐색, DFS 입니다. 이번 포스팅에서는 기본 그래프를 트리로 사용하고 있지만 트리에만 사용할 수 있는 것은 아닙니다. DFS는 이름 그대로 그래프를 탐색함에 있어서 깊이를 우선적으로 탐색하는 방법을 말합니다. DFS의 탐색 순서입니다. 1 → 2 → 4 → 5 → 3 → 6 → 7 의 순서로 탐색을 진행하는 모습을 확인할 수 있는데요. 저는 DFS를 보면서 호기심이 많은 사람이다 라고 생각했던 기억이 있습니다. 각 노드를 하나의 방이라고 보고 간선이 문이라고 한다면 깊.. 2023. 8. 12. [BOJ][Python]11725번 풀이 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline sys.setrecursionlimit(10**7) def dfs(parent): if visited[parent] == 1: return visited[parent] = 1 for i in adjacency_list[parent]: if visited[i] == 0: ans[i] = parent dfs(i) def bfs(): tmp = so.. 2022. 7. 22. [BOJ][Python]11403번 풀이 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net import sys ssr = sys.stdin.readline sys.setrecursionlimit(10000) def sol(r,c,start): if visited[r][c] == 1: g[start][c] = 1 g[r][c] = 1 return visited[r][c] = 1 visited[c][r] = 1 g[start][c] = 1 g[r][c] = 1 for i in range(n): if g[c][i] == 1: sol(.. 2022. 7. 8. [BOJ][Python]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 import sys input = sys.stdin.readline sys.setrecursionlimit(10000) def sol(v): if visited[v] == True: return else: visited[v] = True for i in range(len(edges)): if edges[i][0] == v: sol(ed.. 2022. 6. 16. [BOJ][Python]1260번 풀이 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque import copy def dfs(v): visited[v][v] = True print(v, end=' ') for i in range(1,n+1): if visited[v][i] == True and visited[i][i] == False: dfs(i) elif visited[i][v] == True.. 2022. 5. 28. [BOJ][Python]1388번 풀이 https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net def dfs(r,c): global cnt if visited[r][c] == True: return visited[r][c] = True if b[r][c] == '-': if c+1 2022. 5. 24. 이전 1 다음 반응형
