Algorithm/백준(BOJ)111 [ 파이썬(python) ] 백준 2606 - 바이러스(DFS) 📌 백준 2606 - 바이러스(DFS) 문제 설명 💡 나의 풀이 코드 업에서 풀었던 문제인데, 다시 풀어봤다. DFS를 이용해서 방문하지 않은 노드가 있을 때 cnt를 누적하는 방법으로 구현했다. 중요한 점은 cnt를 전역변수로 사용했기 때문에 파라미터로 전달하지 않았다. import sys input = sys.stdin.readline def dfs(graph, v, visited): global cnt visited[v] = True for i in graph[v]: if not visited[i]: cnt += 1 dfs(graph, i, visited) PC = int(input()) network = int(input()) graph = [[] for _ in range(PC + 1)] vis.. 2021. 4. 19. [ 파이썬(python) ] 백준 11724 - 연결 요소의 개수(DFS) 📌 백준 11724 - 연결 요소의 개수 문제 설명 💡 나의 풀이 이번 문제는 BFS와 DFS 모두 이용해서 풀었는데 시간 차이가 많이 나지 않았다.(근소하게 DFS가 48m/s정도 빨랐다.) 무방향 그래프가 없을 때는 입력값을 반대로 바꿔서 넣어줘도 된다. 예제 입력1을 그림으로 표현하면 다음과 같다. 문제를 쉽게 그림으로 표현했다. graph의 index가 노드이다. DFS로 풀 때는 최대 재귀 값을 더 열어줘야 풀린다. import sys sys.setrecursionlimit(1000000) input = sys.stdin.readline def dfs(graph, v, visited): # dfs implementation visited[v] = True for i in graph[v]: if .. 2021. 4. 19. [ 파이썬(python) ] 백준 11724 - 연결 요소의 개수(BFS) 📌 백준 11724 - 연결 요소의 개수 문제 설명 💡 나의 풀이 이번 문제는 BFS와 DFS를 이용해서 풀었는데 시간 차이가 많이 나지 않았다.(근소하게 dfs가 48m/s정도 빨랐다.) 방향 그래프가 없을 때는 간단하게 입력값을 반대로 바꿔서 넣어주면 된다. 이후에 몇 번 노드끼리 이어졌는지를 graph에 입력하면 되는데 무 방향 그래프기때문에 순서가 바뀌어도 된다. 예제 입력1을 그림으로 표현하면 다음과 같다. 문제를 쉽게 그림으로 표현했다. graph의 index가 노드이다. from collections import deque import sys input = sys.stdin.readline def bfs(graph, start, visited): # BFS implementation queu.. 2021. 4. 19. [ 파이썬(python) ] 백준 2468 - 안전 영역 📌 백준 2468 - 안전 영역 문제 설명 💡 나의 풀이 문제를 이해하는 데는 어렵지 않았지만, 구현하는데 나름대로 어려웠던 문제였다. 아직 구현 실력이 뛰어나지 않아서 그런 것 같다. N의 최대 범위가 100 * 100이어서 시간 복잡도가 O(N^3)이어도 시간초과가 나지 않을 것이라고 판단했는데, 같은 지역에서 내리는 비의 양에 따른 모든 경우를 조사해야 하기 때문에 이중 반복문에서 삼중 반복문으로 늘어났다. 모든 높이를 조사할때는 입력값 중 가장 작은 값부터 가장 큰 값을 범위로 잡았다. 여기서 pythonic코드를 배웠는데 2차원의 배열에서 min, max값을 찾을 때 map함수를 사용하면 간단하게 출력할 수 있다. 반복문 안에서 가장 큰 값의 범위를 설정할 때는 +1을 해주자 아니면 오답 판정 .. 2021. 4. 19. [ 파이썬(python) ] 백준 2331 - 반복수열 📌 백준 2331 - 반복수열 문제 설명 💡 나의 풀이 지금까지 2차원 그래프나 리스트를 이용한 문제만 풀었었는데, 1차원의 수 반복을 이용하는 계산은 새로운 접근이 필요했다. 그래서 어떤 탐색을 사용할까 고민하다 BFS를 사용했는데, 감이 잘 잡히지 않았다. 찾아보니까 DFS를 이용하고, 어떤 코드는 아예 DFS를 사용하지도 않았다. 또, DFS를 이용할 때 Flag 방식을 사용하려고 했는데, 오답 판정을 받았다. 현재 값을 파라미터로 전해주지 않아 그런건지.. 도통 이유를 모르겠다. 제일 하단의 fail코드를 보고 왜 안되는지 아시는 고수님들 댓글 부탁드립니다. ㅠㅠ 😂 😂 DFS - 반복 수열을 진행하며 현재 값을 기준으로 다음 원소를 탐색하고, 이전에 나왔던 원소(중복 원소)가 나올 때까지 다음 .. 2021. 4. 17. 이전 1 ··· 17 18 19 20 21 22 23 다음
