Algorithm Problem

[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. 한칸씩 전전..

[python] 백준 - 14890. 경사로(삼성 SW 역량 테스트 기출 문제)

출처 : BACKJOON ONLINE JUDGE 문제 : https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 1. 하나의 1차원 배열(길)에서 현재위치와 전위치의 높낮이를 비교 (1) 높이가 두칸차이 이상 차이날때 × (2) 높이가 같을 때 ○ (3) 높이가 한칸 차이 날 때 △ 2. 높이가 한칸 차이 날때 경사로를 놓을 수 있는 지 없는 지 확인을 해준다. (1) 경사로를 놓을 수 있는 길이 l 만큼 꼭 지어야 하므로 그만큼 길이 남았는지 확인해준다(인덱스 ..