문제

[Baekjoon] 17142번 : 연구소 3 - Python

Gold 4 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제 풀이 DFS + BFS 처음에 떠올린 방법은 DFS로 활성화 바이러스를 고르는 모든 경우의 수를 탐색하고 입력된 수 만큼 활성화가 되면 그 때 bfs를 호출해서 최단 거리를 구해주는 방법이었다. 딱 봐도 중복된 경우도 탐색하기 때문에 시간이 배로 걸리고 코드도 복잡해지는 방법 ㅎㅎ... itertools의 combinations를 이용해 조합을 구해야 한다. 비활성화된 바이러스를 만나면 활성화된다는 것이 좀 혼란스러웠는데 그냥 그 친구는 무시하고 해주면 ..

[Baekjoon] 23288번 : 주사위 굴리기 2 - Python

Gold 3 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 문제 풀이 DFS + 구현 문제 1) 주어진 방향(처음엔 동쪽)으로 좌표를 이동시키고 범위를 벗어난 경우 반대방향으로 이동시킨다. 2) 이동한 칸의 점수를 획득한다. 3) 주사위 바닥면의 값과 이동한 칸의 값을 비교해 다음 진행할 방향을 정해준다. 이렇게 동작하는 solution함수를 짜줬고, dfs함수를 따로 빼서 점수를 계산할 수 있도록 해주었다. 코드 def dice_move(direction, dice): dice[5], di..

[Programmers] 여행 경로 - Java

Level 3 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제 풀이 BFS도 나올 줄 알았는데.. 이것도 DFS ㅎ 이번 문제는 시작 지점이 인천으로 고정되어 있기 때문에 그 부분을 주의해서 초기 값을 넣어주고 마찬가지로 재귀함수를 돌려주면 된다. 티켓의 사용여부를 표시하기 위해 visited 리스트를 만들어주고 count 변수로 사용한 티켓 수를 확인할 수 있도록 해줬다. route를 저장하고 정렬하는 부분에서 헤매서 구글링을 했는데 정말,, 아직 난 갈길이 멀다. 문..

[Programmers] 단어 변환 - Java

Level 3 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 풀이 DFS 문제 우선 문제에서 주어진 조건대로 철자 하나씩만 바꿔야하기 때문에 두개이상 달라지면 false를 반환하는 함수를 만들어줬다. 그리고 재귀함수에서 한개만 달라지는지 확인하고 그게 맞으면 방문처리하는 식으로 dfs를 구현했다. 몇 개의 단계를 거쳤는지 확인하기 위해 stage 변수를 만들고 target과 같게되면 바로 최소값과 비교해 저장한다. 여기서 주의해야 할 것은 그냥 "=="연산자로..