Python
![[py] 17144_미세먼지 안녕!](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FJPzQf%2FbtsGwM0Wbpa%2FfxOKBJbhVls7KhR71rWFV0%2Fimg.png)
[py] 17144_미세먼지 안녕!
2차원 구현 문제였다. 파이썬으로는 오랜만에 푸는 것 같다 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제에서 주어진 대로 따라가며 구현만 해주면 된다! 1. 확산하기 확산을 할 때 조금 헷갈릴 수 있다. 위와 같이 먼지들이 붙어있는 경우가 있는데 이때는 확산된 상태가 연동되며 미세먼지가 뿌려지는 것이 아닌 한번에 뿌려진다!!! 즉 이전 상태의 먼지 값에만 참조해서 확산을 해주면된다. 2. 청소하기 청소기가 작동하며 먼지들을 한칸씩 밀어..
[JS] 소가 길을 건너간 이유6
그래프와 DFS를 활용한 풀이 https://www.acmicpc.net/problem/14466 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 소와 소를 만나는 과정을 DFS를 활용해서 구하되 가는 길에 다리가 있다면 건너지 않으면 된다. 1. 그래프 설정하기 2. 소를 1:1 대응으로 찾을 수 있는지 분리 3. 각 대응마다 DFS를 활용하여 소에서 소로 갈 수 있는지 확인 includes는 배열의 1차까지만 비교하기 때문에 find를 활용해서 찾아야 한다! con..
16236_아기상어
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 이역시 이해는 하기쉬운 구현문제였다. 하지만 시간을 엄청엄청 많이 잡아먹었다... 다른부분보다 문제되는 부분은 바로 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 해당 부분이다. 이부분을 매우매우 매우 유심해 봐야한다. 처음에는 그저 상,좌,우,하 순서로 bfs를 탐색하면 될줄 알았다. 하지만 이렇게 하면 틀리게 ..
16235_나무제테크
https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 알고리즘보다는 문제를 얼마나 꼼꼼히 읽고 그대로 구현할 수 있냐 문제였다. 되게 어이없는부분에서 막혔었다... 나무가 양분을 먹지 못하는 경우 전체 나무양분의 절반을 가져간다고 생각했는데, 각 개별 나무의 나이의 절반을 양분을 흙에 되돌려 놓기 때문에 한번에 더하면 안된다. 예를들어 [3,3] 와같은 나무 두그루가 죽어야한다고 생각하면 한번에 처리하면 6 // 2 => 3의 양분이..
16234_인구이동
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 꽤나 헤맸었던 문제다.. 처음에는 유니온파인드로 풀까 하다가 결국 같은 집합을 만들어도 그들의 합으로 또 해당그룹의 수를 바꾸려면 두번 일해야한다는걸 깨닫고 그냥 bfs를 사용해서 그때그때 집합을 만들어 구현하였다. 시간초과나 메모리초과때문에 엄청 고생했는데 bfs를 맵에서 검사할때 한바퀴돌때 이미 집합에 넣어서 검사할 필요가 없는부분은 bfs를 검사하면 안되었었고, 특히 bfs안에..
5373_큐빙
https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 상당히 귀찮고 까다로운 문제였다. 이전에 주사위 문제를 풀었던 것과 유사하게 큐브의 전개도를 펼쳐놓고, 각 회전에 따른 방법을 함수로 하나씩 만들어서 구현했다. 문제를 겨우 통과하고 다른사람들 답을보니 함수를 굳이 12개 안쓰고 시계회전을 반시계회전을 3번하는 방식으로 만드는 것을 보았는데 되게 좋은방법이라고도 생각이 들었다.