분류 전체보기74 [백준] 11724: 연결 요소의 개수 python 구현 / DFS, 런타임 에러 (RecursionError), 시간초과 해결 첫 시도에 해결할 줄 알았으나 5번이나 제출하고 해결한 문제 ㅎ 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 사실 문제 이해를 잘 못했다. 나와 같은 사람들을 위해 문제를 위한 그림 첨부 ! 노드와 엣지를 선으로 연결 했을 때 빨간색 그룹과 파란색 그룹, 두 개의 그룹으로 나오게 된다. 이를 "연결 요소"라고 칭하고 그룹의 개수를 세는 문제. 풀이 처음에는 DFS로 풀면 되겠다 싶어서 코드를 작성했건만 RuntimeError와 시간 초과 문제가 나타났다.. 1. RuntimeError (RecursionError) 해당 문제는 sys 모듈을 사용하여 python에서 정의한 재귀의 최대 깊이보다 더 깊게 설정해주면 된다. .. 2023. 3. 2. [백준] 1012: 유기농 배추 python 구현 / DFS, RecursionError 문제 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. => 인접한 배추들의 뭉치(?)의 개수를 세는 문제 풀이 지난 시간에 푼 단지 번호 붙이기 문제와 비슷한 유형이기도 해서 이번엔 DFS로 한번 풀어보고 싶었다.. 그런데 이 선택을 후회한다 ㅠㅠ 기본적으로 python 에서 설정한 재귀의 최대 깊이는 1000이다. 그러나 본 문제에서, 모든 칸에 배추 흰 지렁이(1) 가 있다면, 재귀함수 자체를 50*50 = 2500호출하게된다. ===> 해당 과정에서 RecursionError 질문 게시판에서 찾아봤을 때 재귀의.. 2023. 2. 21. [백준] 2667: 단지번호붙이기 python 구현 / BFS 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. CODE 나는 해당 문제를 BFS 방법론을 통해 구현하였다. 해당 문제에서 주의할 점은 2차원 리스트를 다룸에 있어서, x축과 y축의 방향 설정을 하는 방법이 numpy와는 다르다는 것 ! 추가로 입력을 받을 때 split으로.. 2023. 2. 21. [백준] 2606: 바이러스, python 구현 / 출력 초과 Error 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. code 현재는 adjacency matrix를 사용하여 구현하였지만, 사실 adjacency list를 사용하는 것이 메모리 효율측면에서 월등하다고 한다 ! 만약 가중치를 가지는 그래프라면 Node[1] = [(2, 4), (3, 1), ...] 와 같이 튜플로 (node, weight)를 표현할 수 있음 ! n = int(input()) pair_n = int(input()) adj_mat = [[0]*n for _ in range(n)] for _ in range(pair_n): x, y = .. 2023. 2. 20. 이전 1 ··· 9 10 11 12 13 14 15 ··· 19 다음
