dfs 검색 결과
4 개의 검색 결과가 있습니다.
개발/알고리즘

[백준 15918] 랭퍼든 수열쟁이야!! (python)

15918번: 랭퍼든 수열쟁이야!! 세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n) www.acmicpc.net DFS로 모든 경우의 수를 체크해주면 된다. 2N+1 길이 arr 배열을 만든다. (default = 0) 해당 숫자를 사용했는지 안했는지 체크하는 N+1 길이 used 배열을 만든다. X와 Y자리 숫자는 항상 같으므로 arr[X] = arr[Y] = Y-X-1 로 설정한다. dfs함수를 통해 x가 2N+1이라면 수열이 완성된것이므로 count해준다. arr[x]가 0이 아니라면 이미 숫자가 들어있으므로 다음칸을 계산하는 dfs(x+1)을 실행한다. 숫자가 들어있지 않다면 사용하지 않은 숫자(j) 중에서 arr[x+j+1]에도..

2021. 5. 30. 19:32
개발/알고리즘

[백준 1103] 게임 (python)

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 처음에 DFS만 사용했더니 시간초과가 났다. 다른 사람 코드를 보니 DP를 사용하더라.. 최대값을 구해야 하는 것이니 dp에 값을 저장해 이전값보다 작은 값이면 진행하지 않도록 하자 방문 여부를 저장하는 visited 배열을 생성한다. 움직인 횟수를 저장하는 dp 배열을 생성한다. 시작점에서 네방향으로 움직이되 바깥으로 나가지 않고, 구멍이 아니고, 이전보다 움직인 횟수(cnt+1)가 많다면 진행한다. 만약 방문했던 곳이라면 무한 루프에 돌 수 있으므로 -1 출..

2021. 4. 22. 01:41
개발/알고리즘

[백준 11724] 연결 요소의 개수 (python)

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 DFS로 연결 되있는 것들을 파악하자 이차원배열에 연결되어 있는 것들을 넣어준다 체크했었는지 visited로 흔적을 남겨놓는다 visited 하지 않았다면 answer늘리고 visited에 연결요소들 1로 바꾸어준다 몰랐던 점 - sys.setrecursionlimit(10000) -> 재귀 depth가 정해져있으므로 바꾸어 주어야한다 인접행렬 만들때 0,1로 다 채웠었는데 행마다 값을 넣어주는 방법도..

2021. 3. 19. 23:18
개발/알고리즘

[백준 2606] 바이러스 (python)

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net DFS로 탐색 인접행렬과 방문흔적 남기는 배열을 생성한다 방문하지 않았고, 연결되있는 것들을 체크한다. import sys input = sys.stdin.readline N = int(input()) answer = 0 def dfs(x): global answer for i in range(N+1): if matrix[x][i] == 1 and check[i] == 0: answer += 1 matrix[x][i] = 0 matrix[i][x] = 0 check[..

2021. 3. 19. 18:47