22_블록 이동하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 전형적 happenundo.tistory.com
BFS
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 전형적인 BFS를 이용해서 최단거리를 구하는 문제이다. 다만, 일반적인 BFS 문제와 다른 점은 로봇이 차지하고 있는 위치가 두 칸이며, 가로세로 이동뿐만 아니라, 회전을 통해 이동할 수 있다는 점이다. 나도 BFS를 사용해야 하는 최단거리 문제라는 점은 바로 알았지만, 이를 어떻게 구현해야 할지, 즉, 구현력이 부족한 걸 느낀문제였다. 로봇이 차지하고 있는 위치가 2칸이라고 하더라도, 위치 정보를 관리할 수 있는 방법이 있다. 바로 튜플을 사용하는 것이다. 로봇의 상태를 {(1, 1), (1, 2)} 이런 ..
21_인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경 happenundo.tistory.com
16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀긴 풀었는데, 시간 복잡도가 최악임 BFS를 활용해서, 인구 이동할 수 있는 국가들을 담은 리스트를 반환해주는 함수를 만들어주고, 해당 리스트에 담긴 원소(인구)의 합을 원소의 길이를 나눈 값으로 해당 국가들의 값(인구)으로 바꿔준다. 그리고, 만약, 위 과정을 겪었을 때, 그래프의 원소가 변하지 않았다면, 더 이상 인구이동을 하지 않은 것이므로 반복문을 종료한다. 내 풀이 코드 # 16234번: 인구 이동 from collections impor..
17_경쟁적 전염 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 happenundo.tistory.com
18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net BFS 문제인데 응용해야 하는 문제다. 처음에는 전체 바이러스의 시작점의 위치를 큐에 넣고, 각 바이러스를 한번씩 이동시키면 되는 쉬운문제 아닌가? 라는 생각이 들었고, 구현도 시간이 오래 걸리진 않았다. 하지만 하나의 큐에 각 바이러스의 위치를 넣어서 BFS를 구현할 경우, 바이러스를 구분할 수가 없었다. 이걸 보고, 큐를 여러개 만들어야 하나? 라는 생각이 들었는데, 이러면 큐가 너무 많아지는데? 라는 생각이 들어서 넘겨버렸다. ..
16_연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한 happenundo.tistory.com
14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 안전 구역의 크기의 최댓값을 구하는 문제다. 벽은 3개 설치할 수 있는데, 벽은 안전구역에 설치할 수 있다. 전체 그래프 크기 N*M = 8*8 = n or ny = m: continue # 벽으로 간 경우 if graph[nx][ny] == 1: continue # 다른 바이러스의 칸으로 간 경우 # if graph[nx][ny] == 2: # continue if not visited[nx][ny]: if graph[nx][ny] == 0 or grap..
15_특정 거리의 도시 찾기 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M happenundo.tistory.com
18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net BFS 문제다. 문제에서 모든 도로의 거리는 1이라고 했으니, 모든 간선의 비용이 1인 것이다. 이럴 때는 BFS를 활용해서 최단 거리를 구할 수 있다.(간선의 비용이 다른 경우에는 다익스트라) 노드의 개수 N은 300,000 이하이고, 간선의 개수 M은 1,000,000 이하이므로, 시간 복잡도는 O(N+M)에 의해 완전완전 가능하다. 기초적인 BFS 구현을 통해 풀 수 있는 문제다. 풀이..
