Hello Ocean! 🌼

문제 https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 문제가 굉장히 길고 복잡하다.. 꼼꼼히 읽어보면서 이해하는 시간이 필요하다. 요약하자면, 결과적으로 입력받은 문자열이 (100+1+|01)+ 패턴에 해당하는지 아닌지를 판단하면 되는 문제이다. 풀이 (100+1+|01)+를 쪼개서 보자. 100+1+ = A, 01 = B라고 하면, (A|B)+ 이므로, A나 B가 계속 반복적으로 나타나면 된다. B는 01 자체이고, A 는 100+..

문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트..

문제 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 출력 좋은 수의 개..

문제 https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 풀이 두 배열(before와 after)을 (0, 0)부터 한 칸씩 비교하면서, 값이 다를 때 BFS를 실행해서 before배열의 값을 after배열의 값으로 바꿔준다. 이렇게 BFS를 돌리고 나서도 두 배열에 값이 다른 칸이 있다면, NO이고 아니면 YES이다. 여기서 주의해야 할 점은, BFS를 "딱 한 번" 돌려야 한다는 것이다. 아래 예시를 ..

문제 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 풀이 tree를 이용하여 풀이했다. value와 자식들의 배열을 가지는 Node를 만들었고, 이 Node들을 트리로 연결한 후에 DFS로 탐색했다. 각 Node의 자식들이 오름차순으로 정렬될 필요가 있었다. 따라서 vector대신에 map을 사용했다. map은 기본적으로 key값을 기준으로 오름차순으로 정렬되어 있기 때문이다. 들어온 먹이 정보를 벡터에 저장하고, root부터 ..

문제 https://www.acmicpc.net/problem/17370 17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 곤충 관찰이 취미인 유이는 세 정육각형이 서로 맞닿아 있는 어떤 점 위에 개미를 하나 올렸다. 이렇게 우리에 올라온 개미는 그 자신에게 미지의 영역인 우리를 페로몬을 뿌리며 탐색하기 시작했다. 처음 개미는 점과 연결된 세 변 중 하나를 향해 이동..