Algorithm/DFS&BFS&백트래킹&재귀52 [프로그래머스 lv3] 단어 변환 사용 언어 - Python3 문제 - 단어 변환 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 큐를 활용한 이중 for문 (정답 맞춘 여부 X) 1. 예외처리 원하는 target 값이 words 리스트에 없는 경우, 0을 return 한다. 2. q = deque() 활용 q.append([begin, 0]) = q에 [시작값, 변환횟수] 형태로 입력한다. 각 원소를 x, cnt로 저장하여 while 문에서 처리 words 리스트에서 한 단어씩 확인하면서 x 값과 비교해준다. x[j] != word[j] j번째 알파벳이 다른 경우, diff += 1.. 2023. 4. 22. [Python3] 백준 1697번 숨바꼭질 사용 언어 - Python3 문제 - 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 정답 BFS 재귀함수 (정답 맞춘 여부 X) from collections import deque def bfs(): q = deque() q.append(n) while q: x = q.popleft() if x == k: print(dist[x]) break for nx in (x-1,x+1,x*2): if 0 2023. 4. 19. [Python3] 1189번 컴백홈 사용 언어 - Python3 문제 - 컴백홈 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 정답 nx,ny 이동하는 BFS 만들기 (정답 맞춘 여부 X) dx = [-1,0,1,0] dy = [0,-1,0,1] from collections import deque def DFS(x,y,count): global answer visited[x][y] = 1 if [x,y] == [0,c-1]: #오른쪽 맨 윗(집)도착시 if count == k: #거리가 k라면 조건만족.. 2023. 4. 9. [Python3] 백준 1012번 유기농 배추 사용 언어 - Python3 문제 - 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 정답 nx,ny 이동하는 BFS 만들기 (정답 맞춘 여부 X) 0. 입력 배추밭 graph(m행*n열)에 graph[x][y] = 1로 배추표시 1. queue를 사용한 BFS(x,y) visit 리스트를 만들지 않아도, grpah의 0과 1로 방문표시가 가능하다. graph[x][y] = 0 방문처리 graph[x][y] = 1 방문하지 않은, 배추가 있는 곳 x,y를 상하좌우로 이동시켜 nx,ny의 새로운 위치에서 gra.. 2023. 4. 9. [Python3] 백준 1260번 DFS와 BFS 사용 언어 - Python3 문제 - DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 정답 BFS, DFS 만들기 (정답 맞춘 여부 X) 0. input, 변수 선언 graph = 정점의 개수+1 만큼의 (n+1,n+1) 0벡터 배열을 만들어준다. visit했는지 여부를 (n+1) 크기의 0벡터로 만든다. BFS, DFS 두개의 리스트로 만든다. graph[a][b] = graph[b][a] = 1 입력되는 간선은 양방향이기 때문에 반대방향도 똑같이 1이다.. 2023. 4. 9. [프로그래머스 lv 3] 네트워크 사용 언어 - Python3 문제 - 네트워크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 재귀적인 DFS 문제 (정답 맞춘 여부 X) 1. visited 방문여부 리스트 생성 2. for문을 두개 만들어서 인덱스 com, connect를 비교 값이 1이고, 방문여부가 False인 노드를 또 DFS 재귀함수를 돌리는 구조 com 인덱스를 방문한 후, com에서 connect 인덱스를 방문하기 때문에 DFS(n,computers,connect,visited)로 바뀜 방문한 connect를 기준으로 또 새로운 노드를 방문하려고 하는 재귀함수이다. 3... 2023. 2. 15. [프로그래머스 lv 2] 전력망을 둘로 나누기 사용 언어 - Python3 문제 - 전력망을 둘로 나누기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 완전탐색 BFS 문제 (정답 맞춘 여부 X) 정답 풀이 해당 와이어를 끊었을 때, BFS를 돌려서 한쪽 영역의 노드 수를 구한다. BFS) 해당 노드를 방문하지 않은 경우, 연결된 노드수 result를 구한다. 앞서 저장된 answer값과 현재 result로 구한 노드 간의 차를 비교했을 때, 더 작은 값으로 return 한다. # 정답 from collections import deque def bfs(start,visited,graph): q.. 2023. 2. 10. [프로그래머스 lv 2] 게임 맵 최단거리 사용 언어 - Python3 문제 - 게임 맵 최단거리 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 이동할 때마다 칸의 값을 더해가는 BFS 문제 (정답 맞춘 여부 X) 정답 풀이 1. dx,dy 상하좌우 이동 2. deque()에 (x,y) 튜플형태로 append 한 칸 이동하면, queue에 입력되고 while문으로 popleft된다. 3. queue가 없을 때까지 while문 반복 상하좌우로 이동 nx,ny 이동한 값이 0보다 작거나 len(maps)를 벗어나면 무시한다. continue 이동한 맵 값이 0이라면 무시한다. 1일 경우, 지금까.. 2023. 1. 31. [프로그래머스 lv 2] 타겟 넘버 사용 언어 - Python3 문제 - 타겟 넘버 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 DFS 문제 (정답 맞춘 여부 X) 정답1 풀이 - dfs 문제 1. answer = 0 정답개수 세는 변수 2. dfs 인자 정의 depth = 사용한 숫자개수. 왼쪽숫자부터 한개씩 꺼내서 연산한다. 0에서 시작해서 len(numbers)가 될때까지 반복 numbers = 리스트형태의 input값 target = 숫자형태의 input값 total = 값을 계산한 결과. total이 target과 같다면 정답개수에 추가해준다. 3. 재귀적으로 반복 dfs를.. 2023. 1. 27. [백준] 25501번 재귀의 귀재 사용 언어 - Python3 25501번: 재귀의 귀재 (브론즈2, 재귀) 문제 ★재귀 문제★ 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 정답 문제에 나온 코드를 파이썬으로 구현하는 문제 (코드 풀이) recursion 함수에서 문자열s의 첫(0) 문자와 끝(len(s)-1) 문자가 같은지 재귀적으로 계속 비교한다. 비교하려는 문자열의 인덱스들이 뒷문자가 더 인덱스가 작다면, 1을 return한다. 첫 문자와 끝 문자가 같지않다면, 0을 return한다. 첫 문자와 끝 문자가 같다면, 그 다음 문자들을 비교한다. recursion(s,l+1,r-1) # 정답.. 2023. 1. 23. 이전 1 2 3 4 5 6 다음