개발자 블로그

문제 설명 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 나의 풀이 from collections import deque, defaultdict # 기준이 되는 start_num을 기준으로 너비 탐색을 통해 kavin_bacon리스트의 인덱스 정보를 # 나를 기준으로 얼마나 떨어져있는지 카운트 정보를 담는다. # 현재 숫자가 tartget_num이라면, kavin_bacon의 해당 값을 반환 def bfs(graph, start_num, target_num):..

문제 설명 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 나의 풀이 from collections import deque def find_cycle(graph, start_num, visited): q = deque() q.append(start_num) while q: cur_num = q.popleft() next_num = graph[cur_num] if next_num not in visited: visited.append(nex..

문제 설명 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 나의 풀이 from collections import deque, defaultdict def bfs(start_num): cnt_dict = defaultdict(int) q = deque() q.append(start_num) dx = [-1,1,0,0] dy = [0,0,-1,1] while q: cur_num = q.popleft() if cur_num == '123456780': return cnt_dict[cur_num] zero_idx = cur_num.find('0') zero_x = zero_idx // 3 ze..

문제 설명 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 나의 풀이 from collections import deque, defaultdict def relation_people(people, start_person, relation_graph): q = deque() q.append(start_person) chon_list = [-1] * (people + 1) chon_list[start_person] = 0 while q: cur_person = q.popleft() for pe..

문제 설명 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 나의 풀이 from collections import deque, defaultdict def bfs(start_number, target_number): q = deque() q.append(start_number) distance_dict = defaultdict(int) distance_dict[start_number] = 0 dx = [-1, 1] while q: cur_num = q.popleft() if cur_n..

문제 설명 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 나의 풀이 from collections import deque def changing_graph_zero_one(graph, rain_amount): safety_graph = [[1]*len(graph[0]) for _ in range(len(graph))] for i in range(len(graph)): for j in range(len(graph[0])): if graph[i][j]

문제 설명 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 나의 풀이 from collections import deque def bfs(graph, q): dx = [-1,1,0,0] dy = [0,0,-1,1] while q: y, x = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

문제 설명 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 나의 풀이 from collections import deque def bfs(graph, start_node): if not graph[start_node[0]][start_node[1]]: return False q = deque() q.append(start_node) graph[start_node[0]][start_node[1]] = 0 dx = [-1,1,0,0] dy = [0,0,-1,1] while q: current_y, current_x = q.p..

문제 설명 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 나의 풀이 from collections import deque def bfs(graph, start_node): if graph[start_node[0]][start_node[1]] == "0": return False visited = [] q = deque() q.append(start_node) visited.append(start_node) graph[start_node[0]][start_node[1]] = "0" dx = [-1, 1, 0, ..

문제 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 나의 풀이(시간 초과) s = input() n = int(input()) s_list = list(s) cur = len(s_list) for _ in range(n): user_commend = input() if user_commend[0] == 'L' and cur != 0: cur -= 1 if user_commend[0] == 'D' and cur != len(s_list): cur += 1 if user_commend[0] == 'B' and c..