시작이 반

갈수 있는 여행 경로를 정하는 문제 dfs로 풀었지만 테스트케이스 1번만 통과가 안된다... 무슨 문젠지 모르겠다.. (질문에 있는 모든 케이스 통과) 1번을 통과하기위해서는 같은 티켓이 여러장 있다고 가정하고 풀면된다고 하는데 고려해서 풀었음에도 통과가 안된다.. (ㅠㅠ 못풀었음) def solution(tickets): answer = [] place = list() i = 0 for ticket in tickets: if ticket[0] == 'ICN': ticket.append(i) place.append(ticket) i += 1 place.sort(key=lambda x: x[1]) for j in place: visited = [False] * len(tickets) visited[j[2]..

result = list() def solution(begin, target, words): global result answer = 0 if target not in words: return 0 elif target == begin: return 0 visited = [False] * len(words) dfs(begin, target, words, visited, answer) return min(result) def dfs(begin, target, words, visited, answer): global result if begin == target: return result.append(answer) change = list() for word in words: #바꿀수 있는 단어 찾기 coun..

dfs, bfs를 사용하여 풀수있다. dfs로 문제를 해결하였다. dfs가 끝난이후 해당 node를 방문했는지 확인하고 그룹수를 증가시킨다. visited = list() def solution(n, computers): global visited visited = [False] * n answer = 0 for i in range(n): if not visited[i]: dfs(n, computers, i) answer += 1 return answer def dfs(n, computers, start): global visited, count visited[start] = True for i in range(n): if computers[start][i] == 1 and not visited[i]: ..

재귀 문제이다. dfs로 문제를 풀었다. 한 숫자에 대해서 양수 or 음수를 더할수 있다. 마지막 depth에 도달했을때 target과 같으면 count 를 증가시킨다. count = 0 def solution(numbers, target): dfs(numbers, target, 0, 0) return count def dfs(numbers, target, depth, result): global count if depth == len(numbers): if result == target: count += 1 return left = result - numbers[depth] right = result + numbers[depth] dfs(numbers, target, depth+1, left) dfs(..

NxN행렬을 검사한뒤 일괄된 숫자가 아니면 9등분 하는 문제이다. 9등분한 행렬을 각각 다시 재귀를 돌려서 검사한다. 백준 1021번 문제와 유사한 문제이다. tmdrl5779.tistory.com/100 [백준] 1021번 (python 파이썬) ex) 10 3 2 9 5 2 queue = 1 2 3 4 5 6 7 8 9 10 왼쪽으로 회전 1번 queue = 2 3 4 5 6 7 8 9 10 1 pop 9 queue = 3 4 5 6 7 8 9 10 1 오른쪽으로 회전 3번 queue = 9 10 1 3 4 5 6 7 8 pop 5 queue = 10 1 3 4 5.. tmdrl5779.tistory.com n = int(input()) graph = [list(map(int, input().spli..

백준 2630문제와 같은 문제이다. tmdrl5779.tistory.com/101 [백준] 2630번 (python 파이썬) Divide and Conquer에 대한 문제이다. 1. 해당 종이가 일괄된 색이 아니면 4등분을 한다. 2. 4등분된 종이를 다시 검사한다. 1, 2를 일괄된 색일때까지 반복한다. 처음 푼방법 종이를 모든 수에 대해 검사 tmdrl5779.tistory.com 출력부분만 고려하면 된다. n = int(input()) graph = [list(map(int, input())) for _ in range(n)] def dnc(x, y, n): check = graph[x][y] for i in range(x, x + n): for j in range(y, y + n): if chec..

Divide and Conquer에 대한 문제이다. 1. 해당 종이가 일괄된 색이 아니면 4등분을 한다. 2. 4등분된 종이를 다시 검사한다. 1, 2를 일괄된 색일때까지 반복한다. 처음 푼방법 종이를 모든 수에 대해 검사하고 4등분된 종이를 list로 만들어서 다시 재귀를 돌렸다. n = int(input()) graph = [list(map(int, input().split())) for _ in range(n)] blue_count = 0 white_count = 0 def makePaper(graph): if validPaper(graph): return left_top = list() right_top = list() left_bottom = list() right_bottom = list() ..

ex) 10 3 2 9 5 2 queue = 1 2 3 4 5 6 7 8 9 10 왼쪽으로 회전 1번 queue = 2 3 4 5 6 7 8 9 10 1 pop 9 queue = 3 4 5 6 7 8 9 10 1 오른쪽으로 회전 3번 queue = 9 10 1 3 4 5 6 7 8 pop 5 queue = 10 1 3 4 5 6 7 8 오른쪽으로 회전 4번 queue = 5 6 7 8 10 1 3 4 pop 총 횟수 8번 핵심은 오른쪽으로 회전할지 왼쪽으로 회전할지 정하는 것이다. 타겟에 대해 index를 계산하여 판단한다. from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) ..