https://www.acmicpc.net/problem/16946 문제조건N×M의 행렬로 표현되는 맵0 : 이동가능, 1 : 벽각각의 벽에대해 해당 벽을 부수고, 이동가능한 장소로 바꾼뒤 그 위치에서 이동가능한 칸의 개수접근방법 처음에는 정말 단순하게 모든 벽에 대해서 BFS를 돌렸다가 시간초과가 났다.최악의 경우 1000^3 이면 10억인데,, 대략 10초가량 소요되는 것이다.그래서 어떻게 하면 시간을 줄여가며 해결할까 고민 한 결과,,, visited 배열을 각각 벽에대해 초기화 시켜주는 작업을 안해주면 시간제한에 안걸릴것이라고 생각했다. 그래서 벽을 탐색하는 것이아니라, 맵에서 이동가능한 부분인 0인 값에서 부터 BFS를 진행해서 인접한 벽에 누적으로 값을 더하고, visited배열을 초기화해줄 ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제조건 벽(1)을 무조건 3개를 세운다. 벽은 바이러스(2)가 퍼져 나가는걸 막아준다. 안전영역(0)의 크기가 최댓값은 얼마인가? 접근방법 애초에 입력이 8이하로 너무 작아서 진짜 내 맘대로 구현할 수 있는 문제였다. 처음에는 최대한 깔끔하게 로직을 짤 수 없을까란 생각이 계속 들었지만, 그리디도 아니고, 어느 알고리즘도 적용할 수 없었다. 여기에 시간을 좀 많이 쏟은것 같다. 단순하게 문제조건만 맞춘다면 ..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제조건 목표지점부터 모든 지점에 대해서 목표지점까지의 거리 구하기 너무 당연하게 BFS로 풀이를 시작했다. #include #include using namespace std; int n, m, map[1001][1001], visited[1001][1001], dist[1001][1001]; int dy[] = { -1, 0, 1, 0 }; int ..