방구석프로의 이야기

https://www.acmicpc.net/problem/18428

문제 해결을 위한 과정

이 문제는 BFS로 해결하기보다는 문제의 조건을 따라서 해결하면 더 쉬웠던 문제입니다. 처음에 그래프입력을 받으면서 x인 곳을 blank라는 리스트에 따로 추가하고 T인 곳을 teacher이라는 리스트에 따로 추가를 해줍니다. 선생님들은 상, 하 , 좌, 우 4곳으로 볼 수 있고 방해물이 없다면 그래프의 끝까지 조회할 수 있으므로 방향 리스트인 dx, dy를 만들고 bfs함수를 정의합니다. 각 방향을 끝까지 조회하면서 빈칸인 경우 T로 방문처리를 해주거나, 방해물이 있는경우 그 뒤쪽은 볼수 없는 경우를 처리해주고, 학생을 찾은 경우 바로 bfs함수에서 False를 return해주면 쉽게 해결할 수 있습니다. 학생을 찾지 못한 경우는 True를 return해주면 되겠습니다.

소스코드

https://www.acmicpc.net/problem/14888

문제 해결을 위한 과정

이 문제의 경우 부호에 해당하는 리스트를 따로 만든 후 해당 리스트에서 보호의 순사가 바뀜에 따라 값도 바뀌게 되므로 순서가 중요한 순열로 뽑아야 합니다. 따라서 숫자의 경우 num이라는 리스트를 만들어 넣어주고 부호의 경우 따로 x라는 리스트를 만든 후 permutations를 통해 숫자보다 하나 적게 뽑은 후 ( 3 + 3처럼 부호의 경우 숫자보다 하나 적어야 함) 교차하여 부호와 숫자가 모두 포함이 된 리스트를 만든 후 이를 계산하는 calc함수를 구현하면 쉽게 해결할 수 있습니다.

문제 해결을 위한 팁

저의 경우 isdigit()를 통해서 부호와 숫자를 합쳐진 리스트에서 구별했는데 이때 int형애는 isdigit()을 사용할 수 없기 때문에 str을 이용하여 우선 다 문자 형태로 바꿔준 후에 isdigit()을 이용하였습니다.

소스코드

https://programmers.co.kr/learn/courses/30/lessons/60058

문제 해결을 위한 과정

이 문제의 경우 재귀를 얼마나 잘 사용할 수 있느냐 그리고 구현 알고리즘을 얼마나 잘 사용할 수 있느냐가 중요한 문제였다고 생각합니다. 문제의 조건을 그대로 꼼꼼하게 코드로 옮기기만 한다면 쉽게 정답을 맞을 수 있는 문제였습니다.

먼저 재귀의 탈출 조건으로 빈 문자열이 들어온 경우 그대로 빈 문자열을 반환하는 것 과

문자열 W를 u, v로 분류하는 것입니다.

이 문제의 경우 균형 잡힌 괄호 문자열을 만드는 함수, 올바른 괄호 문자열인지 확인 하는 함수, solution함수 총 3개의 함수로 구분하여 코드를 작성하면 쉬운 문제였습니다.

균형 잡힌 괄호 문자열로 더이상 분류를 할 수 없게 최소한의 길이를 가진 u를 만들어 낼 수 있도록 균형잡인 괄호 문자열을 만드는 함수 balance함수에서 앞에서부터 몇번째 인덱스에서 최소한의 길이를 가진 균형잡인 괄호 문자열이 만들어지는지를 반환을 해주면 그 반환된 인덱스를 기준으로 리스트를 인덱싱 하여 u와 v를 구분할 수 있습니다.

그 후 u를 다시 올바른 괄호 문자열인지 확인하는 함수 correct를 통해 확인한 후 이 결과에 따라 문제의 조건처럼 재귀를 구현하면 되는 것입니다. 이후 과정은 문제를 소스코드로 그대로 옮기는 것이기 때문에 생략합니다.

소스코드

https://www.acmicpc.net/problem/18405

문제 해결을 위한 과정

이 문제의 경우 BFS만 알고 있다면 쉽게 해결할 수 있는 문제입니다. 그래프를 입력을 받을 때 0이 아닌 즉 바이러스가 있는 부분들에 대한 좌표를 따로 virus라는 리스트를 만들어서 그 리스트에 있는 좌표값들에 대해서만 BFS를 수행하면 되는 것입니다. 이때 문제에서 알 수 있듯이 이미 바이러스가 퍼진 구역에는 어떠한 바이러스도 퍼질 수 없으므로 그래프에서 해당 좌표의 지역이 0 인 경우 즉 비어있는 경우만 탐색을 할 수 있습니다. 또한 문제에서 숫자가 낮은 바이러스가 우선적으로 퍼지는 조건이 있습니다. 이 경우는 문제 해결을 위한 팁에서 알아보겠습니다.

문제 해결을 위한 팁

저의 경우는 바이러스가 있는 곳을 리스트에 넣을때 해당 좌표에 있는 바이러스에 값과 좌표를 리스트에 저장했습니다. 만약 입력 예시 1의 경우 0 행 0열에 있는 바이러스가 1 이기 때문에 virus.append((graph[i][j], i, j)) 이렇게 저장했습니다. 이 형태로 저장을 하게 되면 입력을 다 한 후 virus.sort()를 하게 되면 맨 앞 원소를 기준으로 오름차순으로 정렬을 하기 때문에 별도의 처리 없이 오름차순 된 virus 리스트 그대로 BFS를 수행하면 숫자가 낮은 바이러스부터 우선적으로 탐색을 할 수 있습니다.

소스코드

https://www.acmicpc.net/problem/14502

문제

문제 해결을 위한 과정

이 문제의 경우 조건을 보면 8 x 8로 크기가 제한이 되어있는 것을 알 수 있습니다. 또한 3가지의 벽을 세우는 경우 이므로 64가지의 경우에서 순서에 상관없이 3을 뽑는 즉 64C3이기 때문에 완전 탐색으로 해결해야 함을 알 수 있습니다. 따라서 그래프를 입력받을 때 바이러스인 좌표를 저장하는 리스트와 빈칸을 저장하는 리스트를 각각 만든 후 빈칸의 영역에서 combinations을 사용하여 3개의 구역에 벽을 세운 후 BFS를 이용하여 문제를 해결합니다.

문제 해결을 위한 팁

조합을 이용해 3가지 구역에 대해서 벽을 세운 후 BFS를 수행한 후 다시 벽을 없애주어야 합니다. 그래야 다른 지역에 벽을 세울 수 있기 때문입니다.

소스코드

https://www.acmicpc.net/problem/18352

문제 

문제 해결을 위한 과정

이 문제의 경우 BFS를 통해서 쉽게 해결할 수 있는 문제였습니다. 정답률은 32퍼센트로 좀 낮은 편인데 난이도에 비해서는 정답률이 조금 낮게 나온 것 같습니다. BFS라는 개념을 정확히 알면 쉬운 문제입니다. 만일 BFS를 잘 모르시겠다면 https://bgspro.tistory.com/15?category=981927

한번 보고 오시는걸 추천드립니다. 예시의 그림을 보면 노드가 양방향으로 연결이 된 것이 아닌 단방향으로 연결이 되어있는 것을 확인할 수 있습니다.  시작 지점부터 BFS방식을 통해 탐색을 해 나아가면 예시의 그림을 예로 들면 첫 번째로 탐색이 되는 2, 3 그리고 두 번째로 탐색이 되는 4를 통해 몇 번째로 탐색이 되느냐가 시작 지점 노드 1부터 얼마만큼의 거리가 떨어져 있는지를 의미하는 것이라고 보면 되겠습니다. 따라서 몇 번째로 탐색이 되는지 확인을 한 뒤 입력받은 k와 같다면 어떠한 리스트에 추가를 한 뒤 오름차순으로 정렬을 하면 되는 문제였습니다.

소스코드 

https://programmers.co.kr/learn/courses/30/lessons/60059

문제

문제 설명

고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열 수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

입출력 예

keylockresult

문제 해결을 위한 과정

이 문제의 경우 가장 중요한것은 자물쇠의 크기를 확장시켜야 한다는 것이었습니다. 그 이유는 문제에서 말해주듯이 자물쇠 영역을 벗어난 부분에 있는 열 쇠의 홈과 돌기는 자물쇠를 여는데 영향을 주지 않지만 이라는 문장 때문입니다. 이를 예시를 통해 알아봅시다. 그림은 다음과 같습니다. 파란색 사각형인 자물쇠를 벗어난 부분에 있는 빨간색 키의 부분은 영향을 지 않고 3 X 3 크기인 자물쇠가 딱 맞는 것을 확인할 수 있습니다. 이 문제에서는 이렇게 외부로 나가는 영역을 신경 쓰지 않고 자물쇠의 크기만 모두 차있으면 열림으로 처리힙니다. 

따라서 우리는 자물쇠의 크기를 확대시켜야 한다는것을 알 수 있습니다. 그렇다면 얼마나 키워야 하느냐가 가장 큰 주요한 문제가 될 것입니다. 문제의 조건을 보면 항상 자물쇠의 크기인 N이 열쇠의 크기인 M 이상임을 알 수 있기 때문에 열쇠의 크기는 신경을 쓰지 않고 자물쇠의 크기를 3배로 만들어주면 됩니다. 3배의 크기로 키우면 즉 3 x 3인 경우 9 x 9 크기로 만들어주게 되면 런타임 에러를 걱정하지 않고 키를 자물쇠의 좌상 단부터 우하단까지 모두 맞춰볼 수 있는 것입니다. 이제 문제를 부분으로 나누어 봅시다. 열쇠를 돌리는 부분, 자물쇠가 열리는지 확인하는 부분, 열쇠를 자물쇠에 맞춰보는 부분으로 3가지로 크게 나눌 수 있습니다. 이 부분에 대한 각각의 함수를 작성하면 쉽게 해결할 수 있었습니다. 이렇게 해결할 수 있는 이유는 이 문제가 M의 크기가 20, N의 크기가 20 이 각각의 최대 이므로 모든 경우를 계산하더라도 400회 이기 때문에 완전 탐색으로 해결할 수 있는 것입니다. 

문제 해결을 위한 팁

이차원 리스트를 복사 할 때 deepcopy를 이용하여야 합니다. deepcopy를 이용하기 위해서는 import copy를 넣어주어야 합니다.

소스코드 

BFS란?

BFS 즉 Breath-Frist-Search는 영어를 해석한 그대로 넓이를 우선으로 탐색하는 즉 깊이 우선 탐색입니다.

넓이를 우선 탐색한다는 것은 그래프에서 한 노드에서 연결된 다른 노드들을 퍼져가면서 탐색을 해 나간다는 뜻입니다. 스택을 이용하였던 DFS와 달리 BFS는 큐를 이용합니다. 그림 1을 보시면 이해가 더욱 쉽습니다. 

그림 1에서 노드 1을 시작점으로 BFS를 수행해보겠습니다. (위 예시에서 설명을 용이하게 하기 위해 낮은 숫자부터 방문한다고 가정하겠습니다.)

• 1번을 탐색하고 난 뒤 갈 수 있는곳은 2, 3, 7 이므로 모두 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7) (큐: 2, 3, 7)
• 선입선출을 기준으로 뽑아낸 2번 노드에서 갈 수 있는 곳은 1, 3, 9이지만 이미 1, 3 은 방문처리가 되었으므로 9를 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9) (큐: 3, 7, 9)
• 선입선출을 기준으로 뽑아낸 3번 노드에서 갈 수 있는 곳은 1, 9 이지만 이미 1, 3 은 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9) (큐: 7, 9)
• 선입선출을 기준으로 뽑아낸 7번 노드에서 갈 수 있는 곳은 6, 8 이므로 모두 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9. 6, 8) (큐: 9, 6, 8)
• 선입선출을 기준으로 뽑아낸 9번 노드에서 갈 수 있는 곳은 4 이므로 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4) (큐: 6, 8, 4)
• 선입선출을 기준으로 뽑아낸 6번 노드에서 갈 수 있는 곳은 7 이지만 이미 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4) (큐: 8, 4)
• 선입선출을 기준으로 뽑아낸 8번 노드에서 갈 수 있는 곳은 5, 7 이지만 7은 이미 방문처리가 되어있으므로 5를 큐에 담고 방문처리를 합니다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4, 5) (큐: 4, 5)
• 선입선출을 기준으로 뽑아낸 4번 노드에서 갈 수 있는곳은 9이지만 9는 이미 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4, 5) (큐: 5)
• 선입선출을 기준으로 뽑아낸 5번 노드에서 갈 수 있는곳은 8이지만 이미 방문처리가 되어있다. (탐색: 1, 2, 3, 7, 9, 6, 8, 4, 5) (큐:  )
• 큐가 비어있으므로 탐색을 종료합니다.

탐색이 되는 순서는 위와 같이  1, 2, 3, 7, 9, 6, 8, 4, 5입니다. BFS는 구현을 deque를 이용하여 합니다. 제가 공부를 했던 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with Python에서 코드를 인용하였습니다. 

소스코드