clap0107

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 설명: 처음에 이 문제를 봤을 때는 14502번 연구소 문제처럼 모든 경우의 수의 벽을 부수고 bfs 탐색을 반복하는 방법(백트래킹?)으로 풀려고 했었다. 하지만 연구소 문제와 다르게 테스트 케이스의 최대 개수가 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이고 시간제한은 2초였다. 아직도 시간 계산에 익숙하지 않아서 구글링의 도움으로 시간복잡도를 계산해 ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이: bfs를 사용해야 한다는 것은 눈치챌 수 있었지만 벽을 놓는 조건을 어떻게 구현해야 할지 생각하느라 어려웠다. 처음에는 규칙이 존재하는 줄 알고 조건을 하나하나 적으려고 했지만 경우의 수가 너무 많음을 깨달았다. 그래서 벽을 쌓고 bfs로 탐색하는 과정을 계속 반복하여 모든 경우의 수를 체크하는 방법을 생각했지만 뭔가 이렇게 되면 시간 초과가 날 것 같았다. 그리고 모든 경우의 수를 고려하여 벽을 쌓는..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이: 재귀 dfs를 사용해서 풀었다. 기본 dfs 문제와 달랐던 점은 상, 하, 좌, 우 뿐만 아니라 대각선도 확인해줘야 한다는 것이였다. 그래서 확인 범위를 총 8개로 늘렸더니 성공했다. 앞으로는 재귀를 사용할 때 sys.setrecursionlimit(10**6)를 적어야 한다는 점을 잊지 말아야겠다. import sys sys.setrecursionlimit(10**6) def dfs..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이: bfs를 사용해서 익은 토마토가 하나 있을 때는 정상적으로 작동했다. 하지만 익은 토마토가 여러개일 때는 동시다발적으로 확인해야 했기 때문에 틀렸었다. 답에서 총 익은 토마토 개수를 나눌려고 했지만 어림도 없었다. 그래서 따로 만들어준 bfs함수를 동시에 실행할 수 있도록 멀티쓰레드를 사용해보았다. 성공하나 싶었지만 이것도 메모리초과가 떴다. 결국 구글링의 도움을 받아서 처..