본문 바로가기
728x90

백준 풀이103

[백준/BOJ] - 2644번 python 풀이 - DFS Key Point 1. 함수 dfs의 매개변수를 start 와 count 두개로 설정해두고 노드를 이동할 때 마다 count를 늘려간다. 2. p1 노드와 p2 노드가 만났을 때의 count 값을 출력하면 되는 문제. 3. dfs 특성상 한 방향으로 끝까지 들어갔다가 해당하는 노드가 없을 경우 dfs 재귀함수를 호출할 때마다 count 값을 1씩 늘려가던 것을 이전 dfs로 돌아가며 count 값 을 더했던 것이 이전 상태로 돌아가는 점을 인지해야한다. 4. dfs 함수가 마무리 되려면 재귀함수의 마지막 dfs에서 부터 역방향 (마치 stack 처럼) 으로 진행하게 된다. dfs 함수의 마지막에 visited set 자료형에 담긴 해당 값을 remove 시켜주는 동작을 수행하여 방문처리를 취소한다. im.. 2022. 12. 20.
[백준/BOJ] - 1987번 python 풀이 - DFS Key Point 1. dfs 알고리즘에 대해 정확히 아는지 여부가 중요한 문제이다. 2. (0,0) 위치에서 시작하여 동서남북으로 갈 수 있는 방향으로 진행하며 진행 1회당 cnt를 1 증가시킨다. 3. 이동했을 경우 이동한 알파벳을 visited set에 저장시킨다. 4. golbal value인 ans와 cnt를 비교하며 계속 max 값을 갱신한다. 5. 끝에 도달했을 때의 max 값이 정답 max 값이 아니더라도 재귀 함수 특성상 이전 함수로 이동하여 cnt를 증가시킨 부분이 무효화 되고 그 노드에서 동서남북으로 갈 수 있는 위치를 찾아 진행한다. 6. 맨 처음 선택한 방향이 정답 max 값이 아니더라도 모든 경로를 탐색하는 dfs 특성상 찾을 수 밖에 없는 구조이다. 7. 다만 알아야 할 점은 .. 2022. 12. 19.
[백준/BOJ] - 2583번 python 풀이 - DFS Key Point 1. 배열의 시작점과 이 문제의 예시 사진의 시작점이 달라도 상관 없기에 (직사각형의 위치가 반전되더라도 결과를 도출하는데 영향 없음) 직사각형에 해당하는 범위를 다른 숫자로 예외처리 해준다. 2. 본인은 전체 배열의 값을 모두 1로 설정해주었고 직사각형에 해당하는 부분을 0으로 변경해주었다. 3. 배열에서 1에 해당하는 부분을 찾았을 경우 그 부분을 기점으로 dfs 알고리즘을 적용시켜 몇개의 영역이 도출되는지 확인한다. 알게 된 문법 dx,dy를 set형으로 표시해도 문제를 푸는데 이상 없음 import sys input = sys.stdin.readline sys.setrecursionlimit(100000) cnt = 0 dx,dy = (-1, 1, 0, 0), (0, 0, -1 .. 2022. 12. 19.
[백준/BOJ] - 11724번 python 풀이 - DFS Key Point 1. 0번 index는 헷갈리니 안 쓸 거기 때문에 열을 하나 더 만들어준다. 2. 동떨어진 노드(다른 노드와 연결 되지 않은 노드)가 있을 수 있으니 예외처리 해준다. import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) n,m = map(int, input().split()) cnt = 0 visited = [False] * (n+1) #0번 안 쓸거임 graph = [[]*0 for _ in range(n+1)] def dfs(node: int): visited[node] = True for item in graph[node]: if not visited[item]: dfs(item) for _ in range(.. 2022. 12. 18.
[백준/BOJ] - 4963번 python 풀이 - DFS Key Point 1. 가로, 세로 뿐만 아니라 대각선 까지 섬 하나라 인정한다고 했으므로 dx, dy list 선언할 때 고려 2. 육지인 위치에 도착하면 상하좌우 대각선 모두 육지 존재 여부 확인 후 있을 경우 재귀함수 호출 후 같은 동작 반복 알게 된 점 1. sys.setrecursionlimit을 통해 재귀 limit을 걸어줄 수 있다. import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) #재귀 limit 걸어주기 dx = [1, -1, 0 ,0, -1, -1, 1, 1] #대각선도 인정하는거 인지 dy = [0 ,0 , 1, -1, -1, + 1, -1, 1] cnt = 0 def dfs(x,y): global cnt ma.. 2022. 12. 16.
[백준/BOJ] - 2606번 python 풀이 - 첫 DFS 문제 Key Point 1. dfs, bfs 등 그래프 탐색 문제를 통해 해결 가능한 문제이다. 2. 1번 컴퓨터부터 시작하지만 본인은 cnt에 포함하지 않는다. 알게 된 점 - 인접한 노드의 쌍이 주어지면 양쪽 노드의 입장을 생각하여 append 해주어야한다. (1번하고 순서 바꿔서 1번 더) visted = [False] * (n+1) # +1 하는 이유는 0번 idx도 존재하기 때문 - 배열 하나에 False라는 값이 n+1개 append된다. network=[[]* 0 for _ in range(n+1)] #0번 안쓰니까 1 늘려줌 - 해당 문법을 사용하면 반복문 앞에 숫자는 어떤 값이 와도 상관 없고 몇번 도는지에 따라 리스트 속 리스트 개수가 달라진다. import sys input = sys.st.. 2022. 12. 4.
728x90

티스토리툴바