유형: 그래프 문제: https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 풀이 문제를 이해하는게 조금 시간이 걸린다. 판자는 가로/세로 두 타입이 있고 바닥 장식을 만들 때 사용된다. ---- 의 경우에는 가로형 판자 한개만 있으면 된다. -|||의 경우에는 가로형 판자 1개, 세로형 판자 3개가 된다. search 함수에서는 처음 입력이 가로/세로 어느 쪽인지 판단하고 세로면 x의 인덱스를 1씩 추가하여 탐색, 가로면 y의 인덱스를 1씩 추가하여 탐색했..
유형: 그래프, BFS 문제 Small: https://www.acmicpc.net/problem/16173 문제 Large: https://www.acmicpc.net/problem/16174 16174번: 점프왕 쩰리 (Large) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 입출력 형식 main에서 입력을 받아오고, solution 함수에서 계산함. 이후 풀이는 solution 부분 코드만 올림. #include "iostream" #include "vector" #include "queue" using namespace std; string s..
유형: 그래프, 완탐 문제: https://www.acmicpc.net/problem/14397 14397번: 해변 단위 정육각형 이루어져 있는 지도가 주어졌을 때, 해변의 길이를 구하는 프로그램을 작성하시오. 해변은 정육각형의 변 중에서 한 쪽은 물인데, 한 쪽은 땅인 곳을 의미한다. www.acmicpc.net 풀이 문제에 주어진 문자열을 물이면 1, 땅이면 0인 2차원 벡터로 변환했다. 육각형 형태라, 한 노드의 주변 노드까지 합치면 꽃모양이 된다. (주변 노드는 최대 6개이기에) 2차원 벡터의 모든 노드를 탐색하면서, 땅일 경우에만 주변 노드중 바다인 것만 세주면 된다. 주의할 점은, 노드가 세로 몇째 줄이냐에 따라 주변 노드가 달라진다는거다. 그렇기에 짝수번째, 홀수번째 노드의 주변 노드 위치를..
유형: 그래프, BFS 문제: https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 1 처음 생각해낸 풀이. 큐에 좌표뿐만 아니라 카운트 수도 저장했다. 초기 코드는 메모리 초과로 실패했는데, 방문처리를 큐에서 pop할 때가 아니라 파생위치를 큐에 넣을 때 해줘야한다. 왜냐하면, 큐에서 pop할 때 방문처리를 하면 큐에 있는 원소들은 전부 방문하지 않았다는 전제가 깔린다. 따라서 큐에 좌표가 중복으로 들어갈 수도 있어서, 불필요한 탐색이 많아진다..
