분류 전체보기

[python] 백준 - 1922. 네트워크 연결

문제 해결 1. 오늘 배운 최소 신장 트리(MST)를 사용하는 그래프 문제다. ( + heapq 모듈 사용 ) 💨 그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다. (1) 먼저 간선과 가중치를 인접리스트로 만든다. (2) key, mst, pq | 최소 가중치를 갱신하는 배열, 방문 배열, 힙큐( 최소값을 뽑는 모듈 ) 2. 시작점( 노드중 아무거나 )을 힙큐에 넣어주고 시작 - 이 문제에서는 모든 노드를 연결할 수 있다. (1) 힙큐 안에서 가중치가 가장 낮은 정점을 pop (2) 방문했는지 확인 | 이미 방문을 했다면 continue 를 통해 힙큐에서 다시 뽑고, 아니라면 True로 바꿔주고 가중치를 결과에 더해준다...

[python] 백준 - 2644. 촌수계산

문제 해결 1. 노드간의 최단거리를 구하는 그래프에 관한 기본적인 문제이다. 2. 먼저 주어진 부모자식들 간의 관계를 가지고 인접리스트를 만든다. 3. visit 배열을 만들어 방문 여부를 가지고 DFS 재귀함수를 진행한다. (1) 현재 노드에 인접한 노드를 for문을 통해 뽑아주고, (2) 만약 인접한 노드가 아직 방문하지 않은 상태라면, 그 노드로 이동 - 재귀 (3) 이동한 노드가 구해야하는 노드라면 방문한 노드들의 갯수를 세어주고 결론을 도출. -> 쉬운 문제라고 생각했는데 한참동안 '틀렸습니다'를 얻었다. 이번에도 역시 이웃님의 도움을 받았다. `촌수관계를 나타내지 못하면 -1을 출력해라`....... 문제를 잘 읽어보는 습관을 들여야겠다. 소스 코드 n = int(input()) a, b = ..

[python] 백준 - 17142. 연구소 3 (삼성 SW 역량 테스트 기출 문제)

문제 해결 1. 모든 바이러스의 위치와, 바이러스를 퍼뜨릴 구역의 수를 저장한다. 2. combinations 함수를 이용해 바이러스를 활성화시키는 경우의 수를 만든다. 3. 경우의 수를 하나하나씩 체크한다. (1) bfs를 이용해 바이러스를 모두 퍼뜨리며, 숫자를 1씩 증가시켜주고 마지막 숫자를 가져온다. (2) 바이러스를 다 퍼뜨렸는지 아닌지 검사를 해주고, (3) 최소값을 비교해준다 -> 여기서 주의 할 점은 바이러스를 다 퍼뜨렸음에도 불구하고 비활성화된 바이러스가 있다면 퍼뜨리기 위해서 시간을 소비하여 정답이 나오지 않을 수 있다. 그래서 처음에 바이러스를 퍼뜨릴 수 있는 구역의 수를 저장했고, bfs를 돌면서 바이러스를 퍼뜨린 수와 퍼뜨릴수 있는 구역의 수가 같아지게 되면 멈추어준다. 소스 코드..

[python] 백준 - 14499. 주사위 굴리기(삼성 SW 역량 테스트 기출 문제)

문제 해결 1. 회전방향에 따라 주사위의 숫자위치 변화를 잘 이해해야 한다. (1) 먼저 지도 위에서 주사위를 방향에 맞게 움직여주고 (2) 움직임에 맞게 주사위의 면에 써진 숫자들의 위치를 변경해준다. (3) 바뀐 숫자들과 지도에 써진 숫자를 비교하여 바꿔준다. - > 회전시킨 주사위 면의 변화를 잘 몰라서 그림판에 그려가며 하드코딩 했다.........(어쩔 수 없었다) 소스코드 def move(i, j, direc): global x, y if direc == 1: # 동 if j + 1 = 0: y = j - 1 elif direc == 3: # 북 if i - 1 >= 0: x = i - 1 elif direc =..

[python] 백준 - 17144. 미세먼지 안녕!(삼성 SW 역량 테스트 기출 문제)

문제 해결 1. 먼지를 동시에 확산시킨다. (1) 똑같은 크기의 0으로 채워진 임시 2중 배열을 만든다. (2) 확산시킬 양만큼 임시 배열에 더해준다. ( 그렇게 하면서 확산시킨양만큼 원래의 배열에서 빼준다. ) (3) 확산이 모두 완료되면 임시배열에 있는 값을 원래 배열에 더해준다. 2. 공기청정기 | 먼지를 빨아들이는 방향으로 생각해보자. (1) 공기청정기에서 화살표의 역방향으로 차근차근 이동한다. (2) 이동하면서 다음위치에 먼지가 있으면 현재위치에 덮어씌워준다. -> 처음에 먼지를 확산시킬 때 기존의 먼지가 있는 곳은 확산이 안된다고 혼자 착각을 해서 문제를 이해하는데 많은 시간이 걸렸다. (이웃님이 명쾌하게 알려줘서 금방 해결!) -> 공기청정기가 자기 자신으로 돌아올수 있도록 x의 탐색 범위를..

[python] 백준 - 1987. 알파벳

출처 : BACKJOON ONLINE JUDGE 문제 : https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 www.acmicpc.net 문제 해결 1. DFS/BFS 를 활용하는 방법과 백트래킹을 활용하는 방법 중 하나를 사용하면 된다. ( 여기서는 백트래킹을 사용했다. ) 2. 함수 인자로 ( x좌표, y좌표, 지나가면서 늘어가는 단어) 이 3개를 받는다. 3. 상하좌우 방향을 탐색하면서, 이미 가지고 있는 단어에 포함되어 있는 문자인지 확인해주고 4. 한칸씩 전전..