[백준] 16946 벽 부수고 이동하기 4 | BFS | Gol2 Pythonhttps://www.acmicpc.net/problem/16946 채점 되게 천천히 됨 쫄깃하네여..ㅎ골드 쯤 되니까 시간제한이 문제가 되기 시작한다 ㅎ허허 구상유형 : bfs [문제 해석]벽이 존재하는 맵이 주어짐. 각 벽마다 벽이 없어졌을 때, 해당 벽 위치에 인접한 공간 크기를 구하는 문제빈 공간은 0, 벽은 1벽 위치에 해당하는 공간 크기를 10으로 나눈 나머지를 출력시간제한 : 2초구상 1 (timeout)전체를 돈다벽(1)이 나오면 해당 벽에 인접한 공간을 bfs 돌며 공간 크기를 계산한다벽 위치에 공간 크기를 10으로 나눈 나머지를 기록한다 구상 2 (성공)전체를 돈다방문 전인 빈 공간(0)이 나오면 bfs 인접한..
BFS
[백준] 2146 다리만들기 | BFS | Gol3 Pythonhttps://www.acmicpc.net/problem/2146 pypy로만 성공한 풀이입니다.(python은 시간초과)구상유형 : bfs비슷한 문제들을 푸는 중이라 접근은 어렵지 않게 했으나조건문 하나 잘못적어서 시간 진짜 많이 썼다 도륵시간초과만 나서 시간을 줄이는 방법만 고민했는데 코드에 잘못된 부분이 있었다코드에 논리적인 오류가 있어도 오답이 아닌 시간초과만 날 수도 있다는 것을 깨달은 시간,,,pypy로만 통과했지만 핵심적인 문제는 찾았고 더 이상 시간복잡도 개선에 시간을 쓰는 건 무리라고 판단. 넘어가자! [문제 해석]땅과 땅을 연결하는 가장 짧은 다리 길이 찾기다리와 인접해있으면 연결된 것임시간제한 2초 구상전체를 2번 돌아야 ..
[백준] 13549 숨바꼭질 3 | BFS | Gol5 Pythonhttps://www.acmicpc.net/problem/13549 구상유형 : bfs직전에 푼 1697과 유사그래서 좀더 깔끔하게 풀 수 있었다! [문제 해석]1697 숨바꼭질 문제와 동일하나, 2배 이동을 하는 경우 드는 시간이 0이라는 점만 다르다.N에서 K로 가는 가장 빠른 횟수 찾기한 횟수에 할 수 있는 이동의 종류는 3가지+1-12배 0 ≤ N, K ≤ 100,000시간제한 2초메모리제한 512 MB 구상매번 세가지 경우 모두 bfs 돈다단, 아래 조건을 만족하지 않으면 큐에 넣지 않는다.이미 방문했던 숫자의 경우 이전의 해당 숫자까지 갔던 최소이동횟수보다 클 때숫자가 이동 가능 범위를 벗어날 때 (0 ≤ N ≤ 100,000)..
[백준] 1697 숨바꼭질 | BFS | Sil1 Pythonhttps://www.acmicpc.net/problem/1697 구상유형 : bfs메모리 초과는 처음봐서 고생했다. 문제 조건을 잘못이해했음..~ 그래도 배운 게 있으니까TIP : dict, set보다 처음부터 초기화해서 쓰더라도 list가 더 메모리 적게 쓰고 빠를 수 있다.Q : 아니 다들 visited체크를 해서 한번 방문한 노드는 다시 방문하지 않게 짜는데, 그게 왜 되지?? 더 최적으로 방문한 경로가 답이면 답이 걸러지지 않나 [문제 해석]N에서 K로 가는 가장 빠른 횟수 찾기한 횟수에 할 수 있는 이동의 종류는 3가지 1. +1 2. -1 3. 2배0 ≤ N, K ≤ 100,000 -> 이게 처음 주어지는 위치..
[백준] 2667 단지번호붙이기 | DFS,BFS | Sil1 Pythonhttps://www.acmicpc.net/problem/2667 구상유형 : dfs (bfs도 가능할듯) [문제 해석]연결된 그룹의 수와 크기를 세는 문제가로세로로 인접되어있으면 같은 그룹임그룹의 총 개수 셈각 그룹마다 몇개가 포함되어있는지 개수 셈시간제한 1초5 구상칸 전체를 돈다visited면 넘어간다방문 전이면서 1인 칸을 만나면 dfs시작그 주변에 있는 1인 칸만 스택에 넣으며 dfs돈다 두두두돌면서 1 대신 해당되는 그룹 번호로 바꿔준다 (0,1은 이미 입력데이터에서 사용중이므로 그룹 번호는 2부터 사용)dfs끝나면 칸 전체 돌기를 이어서 진행 트러블 슈팅문제 구상에서 실수해서 한번 헤맸다 dfs bfs도 아직 멀었구나..
[백준] 11725 트리의 부모 찾기 | Sil2 | BFS,DFS Pythonhttps://www.acmicpc.net/problem/11725 bfs dfs 까먹을 것 같아서 몸풀기!세가지 방법으로 풀어보았다. 구상풀이 1 : dfs - 재귀 (71496KB, 336ms)파이썬 재귀 깊이 제한을 조정하는 코드를 추가해서 통과했는데, 부하가 있는 것 같아 다른 방법도 풀어보기로풀이 2 : dfs - stack (61568KB, 312ms)풀이 3 : bfs - queue(deque) (62040KB, 300ms)성능은 채점시마다 약간의 오차가 있는걸 감안하면, 세가지 풀이에 그렇게 큰 차이는 없는 듯 하다.그래도 역시 bfs가 젤 빠르게 나오긴 했다만출력문으로 print말고 더 빠르다는 sys.stdo..
[백준] Gol4 | BFS, 이진탐색? | 2412 암벽등반 Pythonhttps://www.acmicpc.net/problem/2412 구상 main idea는 bfs최소경로찾기, 거기에 이진탐색을 쓰면 시간을 더 줄일 수 있음bfs만 써서 풀어봄이게 왜 이진탐색???→ 최소거리 찾는 거 자체는 bfs 해주면 되는데, 간선 데이터가 주어지지 않아서 다음 노드 찾기에 이진탐색을 쓸 수 있음이진탐색 : 홈을 정렬하고, 이진탐색으로 현위치에서 이동 가능한 최소&최대 홈을 구한다. 그 후 정렬된 홈 목록에서 최소&최대 홈 사이의 홈들만 탐색하도록 한다!.→ 이진탐색 안써도 풀리는 문제ㅇㅇ트러블 슈팅시간초과다음 노드를 찾을 때 노드를 모두 확인하는 게 아니라 원하는 숫자 범위 안에 노드가 존재하는지 탐색하..
