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

https://www.acmicpc.net/problem/2234 문제조건 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다.이 성에 있는 방의 개수가장 넓은 방의 넓이하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 각각 구하시오접근방법 전체 맵을 탐색한다는 점에서 BFS를 떠올릴 수 있었고, 1(2^0), 2(2^1), 4(2^2), 8(2^3) 로 진행할수 있는지 판단해야한다는 점에서 나에겐 조금 생소한 비트마스킹이 생각났다. 이 문제에서 핵심은 비트를 1부터 왼쪽으로 Shift연산을 통해 벽에 대해 나타낸 숫자와 &연산으로 겹치는 지..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제조건 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우, 반..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제조건 (1,1) 에서 (n,m)까지 최단경로 벽을 하나까지 부술수있다. 조건 2 때문에 일반적인 bfs로 풀수가 없다. 벽은 부숴도 되고, 안부숴도되고 그렇다면 어떻게 하지,,? 생각을 해보면 bfs자체가 수행될때마다 최단거리를 의미하고, 그에따라 queue에 넣을 조건만 추가해주면 된다. 벽은 하나까지 부술수있으므로, 배열을 3차원배열로 만들어주고, queue에도 (..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제조건 수빈이와 동생이 있다. 걷는다 : X+1 or X-1 (1초) 순간이동 : 2 * X (0초) ☞ 시간 안걸림 수빈이가 동생을 찾는 가장 빠른시간? 문제를 보고 수빈이와 동생이 아닌, 출발지와 목적지로 생각을 바꿔봤다. 그러면 문제가 평소에 익숙하게 보던 최단거리 찾기가 된다. 그러나, 일반적인 최단거리 찾기와 다른 점은 순간이동을 할때는 시간이 안걸..

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 ..