문제요약 나의 코드 및 설명 import sys sys.setrecursionlimit(10**6) def dfs(sn): for i in board[sn]: if visited[i] == 0: visited[i] = sn dfs(i) n = int(input()) board = [[] for _ in range(n+1)] for _ in range(n-1): s,e = map(int, input().split()) board[s].append(e) board[e].append(s) visited = [0]*(n+1) dfs(1) for start_node in range(2,n+1): print(visited[start_node]) 피드백 DFS 연습을 위해 풀어본 문제. 문제를 처음 보고 이해가 잘 ..
문제요약 나의 코드 및 설명 01 - DFS import sys sys.setrecursionlimit(10**6) def dfs(sx,sy): board[sy][sx] = 0 visited[sy][sx] = 1 if sx >= 50 or sy >= 50: return for i in range(8): nx = sx + dx[i] ny = sy + dy[i] if nx=h: continue else: if visited[ny][nx] == 0 and board[ny][nx] == 1: dfs(nx,ny) while True: w, h = map(int,input().split()) if w == 0 and h == 0: break board = [] for _ in range(h): board.appen..
문제요약 나의 코드 및 설명 from collections import deque def bfs(start, end): queue = deque() queue.append(start) #현재 좌표 값 큐에 추가 visited[start] = 1 #현재 좌표 방문처리 while queue: now = queue.popleft() if now == end: #목표 층에 도달하면 return visited[now]-1 #룩업테이블의 현재 좌표 값 -1 for i in (now+u, now-d): #위로 가거나 아래로 가는 두 가지 if 1
문제요약 나의 코드 및 설명 01 - DFS def dfs(s, count, temp_list): #방문한 노드를 temp_list에 담는다 global ans if end in temp_list: ans = count return #리턴필수! 그래야 더 이상 다음 노드 안 담음! for i in graph[s]: if i not in temp_list: #temp_list에 i가 안 담겨 있다면 dfs(i, count+1, temp_list+[i]) n = int(input()) start, end = map(int, input().split()) m = int(input()) graph = [[] for _ in range(n+1)] for _ in range(m): x, y = map(int, in..
문제요약 나의 코드 및 설명 def dfs(n, start, temp_list): if len(temp_list) == 6: #전달받은 임시 리스트 길이가 6이라면 result.append(temp_list) #추가 return if n == count: return for i in range(start, count): dfs(n+1, i+1, temp_list + [num_list[i]]) while True: num_list = list(map(int, input().split())) if num_list == [0]: #0을 입력받는다면 반복문 탈출 break count = num_list.pop(0) result = [] dfs(0,0,[]) for i in result: print(" ".joi..
문제요약 나의 코드 및 설명 BFS(너비우선탐색)을 활용하여 문제를 해결하였다. bfs 함수를 통해 직사각형이 없는 좌표(1)를 직사각형이 있는 좌표(0) 값으로 바꿔주고, 이중 for문을 통해 아직 바뀌지 않은 좌표가 있다면 bfs 함수가 실행될 수 있도록 구현하였다. from collections import deque def bfs(sx,sy): global num queue = deque() queue.append((sx,sy)) visited[sy][sx] = 1 board[sy][sx] = 0 num = 1 while queue: x,y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx=m: continue els..
문제요약 나의 코드 및 설명 이전까지 풀어본 백트래킹 문제와 크게 다르지 않다. 다만 주의할 점은, 수열의 합(s)이 0이 되는 경우의 수를 구할 때, 빈 리스트의 경우는 제외시켜주어야 한다. len(temp_list) != 0 으로 간단하게 제외시켜줄 수 있었다. def dfs(count, start, temp_list): global ans if len(temp_list) != 0 and sum(temp_list) == s: ans += 1 if count == n: return for i in range(start, n): dfs(count+1, i+1, temp_list+[num_list[i]]) n, s = map(int,input().split()) num_list = list(map(int,..
문제요약 나의 코드 및 설명 문제의 조건 범위(0이상 100000이하)에 해당하는 룩업테이블 visited 리스트를 만들고, 방문 할 때마다 visited 리스트에 저장된 값을 1씩 증가시킨다. 만약 동생을 만나게 된다면, 현재까지의 visited 리스트에 저장된 값에서 1을 빼준 값을 리턴한다. from collections import deque def bfs(sx, ex): global count queue = deque() queue.append(sx) #수빈이 위치 방문처리 visited[sx] = 1 while queue: x = queue.popleft() if x == ex: #수빈이가 동생과 만난다면 return visited[x] - 1 #룩업테이블에 저장된 값-1 리턴 for i in..
