본문 바로가기

분류 전체보기521

[ 파이썬(python) ] 백준 4963 - 섬의 개수(BFS) 📌 백준 4963 - 섬의 개수 문제 설명 💡 나의 풀이 BFS 혹은 DFS만 잘 구현할 수 있다면 어려운 문제는 아니다. 다만, 기존 문제에서는 상, 하, 좌, 우 패턴이 등장했다면 이번에는 대각선 패턴이 등장했다. 이왕 등장했으니 다음 세 가지 패턴을 알아보자. 상, 하, 좌, 우 패턴 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] 대각선 + 상, 하, 좌, 우 패턴 dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] 대각선 패턴 dx = [-1, -1, 1, 1] dy = [-1, 1, -1, 1] 패턴2를 사용하면 쉽게 해결할 수 있다. 그리고 while문 종료조건은 입력이 0, 0이어야 하는데, 이는 if n.. 2021. 4. 20.
[ 파이썬(python) ] 백준 7576 - 토마토(BFS) 📌 백준 7576 - 토마토 문제 설명 💡 나의 풀이 나의 수준에서는 어려웠다... 익은 토마토가 1개일 경우에는 잘 구할 수 있었는데, 2개 이상인 경우는 도저히 생각이 나지 않았다. 그래서 다른사람의 코드를 조금 참고했는데 BFS를 동시에 2개를 돌리는 방법은 아예 생각도 못했고 그러다 보니까 함수의 코드도 이전에 풀던 방법과는 조금 달라서 고민하며 문제를 푸느라 반나절을 쏟아버렸다. 처음에 익은 토마토가 2개 이상 있을 때 케이스를 하나씩 더해서 두 개를 더해주면 될 줄 알았다. 컴퓨팅적으로 생각하지 않고 내키는 대로 생각해버려서 안 되는 방법으로 구현하려니까 머리가 꼬여버렸다. 그리고 문제 마지막에 모든 토마토가 익어있는 상태를 0으로 출력해야하는데, 이 경우는 제외하고 코드를 작성했다. 그래서 .. 2021. 4. 20.
[ 파이썬(python) ] 백준 1926 - 그림(BFS) 📌 백준 1926 - 그림 문제 설명 💡 나의 풀이 BFS를 이용해서 풀었는데, queue에 있는 원소를 pop할 때마다 cnt+=1해주는것을 while문에 쓰지 않고 엉뚱한 곳에 썼다가 답이 안 나와서 헤맸다. 또 중요한것은 함수가 실행될때마다 each_cnt를 1로 초기화 해주자. 아니면 값이 계속 누적된다. 그리고 최대값을 갱신해줄 때 굳이 파라미터로 넣지 않아도 return each_cnt을 해주고 나오는 값과 0부터 max로 비교해주면 나중에 제일 큰 값만 빼낼 수 있다. 가장 간단한 비교방법이니 외워두자. 외부에서 모든 좌표를 하나씩 넣을 때 BFS를 사용하는 조건이 충족되면 cnt+=1 해준다. BFS 함수 내부에서 원소를 pop할때 each_cnt+=1을 해준다. return each_cn.. 2021. 4. 20.
[ 파이썬(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.

티스토리툴바