Hello Ocean! 🌼

문제 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 문제를 요약하자면, 정사각형 모양의 board에서 (0, 0)에서 (N-1, N-..

문제 https://programmers.co.kr/learn/courses/30/lessons/43163 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 ..

문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히..

문제 https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 2차원 맵에서, 출발에서 도착점으로 가는데, X로 표시된 필요한 물건들을 모두 챙겨서 나가는 최소 이동거리를 구하는 문제이다. 풀이 그래프상에서 최소 이동 횟수를 구하는 문제이기 때문에 BFS를 이용했다. 그리고, 그래프상에 X가 있는 지점을 모두 방문하는게 조건이기 때문에 X방문체크를 어떻게 할지 고민하다가, X가 최대 5개라고 해서 길이 5짜리 비트마스크를 이용해서 방문체크를 해주..

문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 [BFS + 구조체] BFS를 이용해서 풀면 되는 문제였다. 일반적인 BFS에서, 상하좌우로 이동하는 것만을 고려했다면, 이 문제에서는 "말 처럼 이동할 수 있는 경우"도 고려해서 BFS를 돌려주면 되는 문제였다. 다만 "말 처럼 움직일 수 있는 횟수"가 K번으로 정해져있으므로, 남은 횟수 k도 큐에 넣어 확인해주었다. * 처음에 visited배열을 2차원으로 만들어서 ..

문제 https://www.acmicpc.net/problem/1194 0에서 출발하여 1까지 갈 수 있는 최단경로를 구하는 문제이다. #은 지나갈 수 없고, a~f는 열쇠, A~F는 문이며 각 문을 지나기 위해서는 해당하는 소문자 열쇠를 가지고 있어야한다. 풀이 열쇠와 문이라는 요소가 추가되기는 했지만, 기본적으로는 BFS를 이용하여 최단경로를 찾는 문제이다. 구조체를 만들어서 BFS를 돌리는것 까지는 비교적으로 금방 할 수 있었는데, 메모리초과가 났다. visited배열을 visited[2][2][2][2][2][2][51][51]로 만들고, 구조체에 6칸짜리 vector를 넣어서 그런 것 같았다. 검색을 해보니, 열쇠 관련 부분을 "비트마스킹"으로 해결해야 하는 문제였다. 따라서 visited배열을..