느낌표 공장

문제 https://www.acmicpc.net/problem/1325 해킹한 컴퓨터 이므로 방문 개수를 반환 return sum(visited) n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): com1, com2 = map(int, input().split()) graph[com2].append(com1) # com2에서 com1을 감염 시킬(방문 할) 수 있다. answer = [] max_v = 0 for i in range(1, n+1): tmp_v = bfs(i) if max_v < tmp_v: # 해킹할 수 있는 컴퓨터 수가 더 많은 경우 answer = [i] # 배열 초기화 max_v =..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 처음 단어에서 목표하는 단어까지 주어진 단어들을 활용하여 최소 변환을 해야 하는 문제이다. (변환을 할 수 없다면 0 반환) 따라서 최단 경로 탐색에 적합한 BFS를 활용하여 문제를 해결하였다. 코드 과정은 다음과 같다. 처음 시작 단어와 0(단어 변환 횟수)을 queue에 넣는다. queue에서 맨 처음에 있는 단어와 횟수를 뽑는다. 주어진 단어들의 집합에서 아직 사용하지 않은 ..

문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 과정 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구해야 하므로, 공장 두 곳을 이은 다리들 중 중량 제한이 더 큰 다리를 건너는 것이 좋다. 따라서 입력받은 다리 정보들을 다리의 중량 제한을 기준으로 하여 내림차순으로 정렬하고, 다익스트라를 사용하되 힙에 push 할 때, 중량을 마이너스를 붙여 push 하여 최대..

문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 과정 동영상과 유사도를 가지고 그래프를 만들어 농부 존이 제시한 동영상 v에서 유사도 k 이상으로 이어진 동영상이 몇 개 있는지 묻는 문제이다. 따라서 이어진 동영상의 유사도가 k이상이면 해당 동영상에서 또 이어진 동영상을 탐색해야 하는 과정을 반복해야 하고, 동영상 개수를 세야 하므로 BFS를 활용하였다. 여기서 주의할 점은 존은 두..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결 과정 캐릭터 위치에서 아이템 위치까지의 최단 경로를 구하는 것이기 때문에 BFS를 이용하여 풀었다. 여기서 주어진 직사각형의 간격이 1일 수 있음에 주의해야 한다. 예) rectangle = [1, 1, 2, 4] 그렇게 되면 테두리가 아닌데도 캐릭터가 지나가게 되므로, 이 경우를 방지하기 위해 크기를 2배로 늘려주었다. (물론 직사각형을 그릴 지형, 캐릭..

from collections import deque # 상 하 좌 우 dy = [-1, 1, 0, 0] dx = [0, 0, -1, 1] def bfs(sy, sx, hour): queue = deque([(sy, sx, hour)]) # 시작지점 추가하고 시작 visited = [[0 for _ in range(garo)] for _ in range(sero)] # 방문한 곳 다시 방문하지 못하도록 만든 리스트 visited[sy][sx] = 1 # 시작지점 방문처리 while queue: y, x, hour = queue.popleft() # 좌표 하나 가져오기 for i in range(4): ny = y + dy[i] nx = x + dx[i] if 0

from collections import deque bfs(sx, sy): queue = deque([(sx, sy)]) # 출발지점 넣기 visited[(sx, sy)] = False # 출발지점 방문 처리 while queue: x, y = queue.popleft() # 좌표 하나 빼 if abs(ex-x) + abs(ey-y)

def bfs(i, top_h): global answer if b

DFS 코드 dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def dfs(y, x, room, cnt): global move move = max(move, cnt) # 이동 갱신 for i in range(4): ny = y + dy[i] nx = x + dx[i] # 범위 내에 있고 지금 방보다 1크다면 if 0

# 방향 벡터 / 상, 하, 좌, 우 dy = [1, -1, 0, 0] dx = [0, 0, -1, 1] # 미로탈출 bfs(시작 y좌표, 시작 x 좌표) -> 2의 위치 def bfs(sy, sx): q = [(sy, sx)] # q에 시작 좌표 넣어주고 시작 # q가 빌때까지 반복 while q: now_y, now_x = q.pop(0) # 현재 좌표 q에서 가져오기 (bfs니까 맨앞에꺼) # 상하좌우 탐색 for i in range(4): # 이동해볼 좌표 설정 (현재 위치 + 방향 벡터가 가리키는 곳) next_y = now_y + dy[i] next_x = now_x + dx[i] # 이동해볼 곳이 미로 범위 안에 있다 ? if 0