백준/깊이 우선 탐색
-
백준 1926 python백준/깊이 우선 탐색 2023. 3. 27. 16:45
문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 DFS를 이용한다. 재귀로 풀 경우 메모리 초과가 발생하므로 stack을 이용한다. n,m=map(int, input().split()) I,O=[[*map(int, input().split())] for _ in range(n)],[0,0] def dfs(sx,sy): stack,S=[],0 I[sx][sy]=0 stack.append([sx,sy]) while(len(stack)>0): ..
-
백준 1043 nodejs백준/깊이 우선 탐색 2023. 1. 26. 13:31
문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 사람 수만큼 그래프 G를 만들어 참여한 파티의 index를 저장한다. dfs로 V에 진실을 들은 사람들을 저장한다. 모든 파티 정보 B에 대해 참가자 중 진실을 들은 사람이 있는지 확인하고, 없으면 결과값 o를 더해준다. let [[N], [, ...A], ...B] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')...
-
백준 2661 nodejs백준/깊이 우선 탐색 2023. 1. 18. 12:50
문제 https://www.acmicpc.net/problem/2661 풀이 함수 F로 주어진 수열이 좋은수열인지 확인하며 스택 S에 담는다. 깊이 우선 탐색으로 크기가 작은 순서대로 탐색하며 답을 찾는다. let N = +require('fs').readFileSync('./dev/stdin').toString() let o = '' function F(x) { const l = x.length for (let j = 1; j F(nx) && S.push(nx)) } console.log(o)
-
백준 1520 nodejs백준/깊이 우선 탐색 2023. 1. 12. 12:45
문제 https://www.acmicpc.net/problem/1520 풀이 dfs를 사용한다. 방문 정보를 담은 V 배열에 dp를 적용해 시간 초과를 피한다. (이미 방문했던 길은 dfs를 돌지 않고 V 정보를 받아온다.) V 배열을 -1로 초기화해 경로 개수가 0인 길과 구분한다. let [[M, N], ...I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e => e.split(' ').map(Number)) let V = [...Array(M)].map(_ => Array(N).fill(-1)) function dfs(x, y) { if (x == M - 1 && y == N - 1) return 1 l..
-
백준 1707 nodejs백준/깊이 우선 탐색 2023. 1. 2. 18:14
문제 https://www.acmicpc.net/problem/1707 풀이 BFS나 DFS로 그래프가 이분 그래프인지 확인한다. DFS let [[], ...I] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(e => e.split(' ').map(Number)) let [i, O] = [0, []] while (i []) for (; j < i + E; j++) { const [a, b] = I[j] G[a].push(b) G[b].push(a) } ..