[백준 17267] 상남자

[백준 17267] 상남자

https://www.acmicpc.net/problem/17267

문제 카테고리

BFS

접근 방법

처음에는 벽 부수기 문제 처럼, 왼쪽으로 갈 수 있는 횟수, 오른쪽으로 갈 수 있는 횟수를 Node 정보로 저장하는 방법을 생각했지만 그렇게 되면...

(x, y, l, r) 각 숫자 모두 1000의 크기를 가지므로 평생 풀 수 없다.

따라서 다음과 같은 아이디어를 고안했다. 별로 안어렵다.

한 번의 BFS를 하며 각 x,y에 도달하기 위한 L, R을 기록한다. 문제의 조건에 만족하는 노드만 count한다.

독특하게 처리해야 하는 곳은 "위 아래로 노빠구" 하는 부분이다. 코드 보면 이해하기 쉽다.

도움을 준 문제들

레이저 통신: https://www.acmicpc.net/problem/6087

상남자보다 더 노빠꾸인 레이저 문제다. 여기서 한번에 queue에 다 집어넣는 테크닉을 써먹었다.

코드

vvi A; int N, M, L, R; bool in_board(int x, int y) { return 0 <= x && x < N && 0 <= y && y < M; } int go(int sx, int sy) { vvi RD(N, vi(M, -1)); vvi LD(N, vi(M, -1)); queue> q; RD[sx][sy] = 0; LD[sx][sy] = 0; q.push({sx, sy}); while (!q.empty()) { int cx = q.front().first; int cy = q.front().second; q.pop(); int cr = RD[cx][cy]; int cl = LD[cx][cy]; int nx, ny; // 아래 노빠구. for (nx = cx + 1; nx < N; nx++) { if (A[nx][cy] == 1) break; if (RD[nx][cy] != -1) continue; RD[nx][cy] = cr; LD[nx][cy] = cl; q.push({nx, cy}); } // 위 노빠꾸. for (nx = cx - 1; nx >= 0; nx--) { if (A[nx][cy] == 1) break; if (RD[nx][cy] != -1) continue; RD[nx][cy] = cr; LD[nx][cy] = cl; q.push({nx, cy}); } // 왼쪽으로 한 칸. ny = cy - 1; if (in_board(cx, ny) && A[cx][ny] != 1 && RD[cx][ny] == -1) { RD[cx][ny] = cr; LD[cx][ny] = cl + 1; q.push({cx, ny}); } // 오른쪽으로 한 칸. ny = cy + 1; if (in_board(cx, ny) && A[cx][ny] != 1 && RD[cx][ny] == -1) { RD[cx][ny] = cr + 1; LD[cx][ny] = cl; q.push({cx, ny}); } } int ans = 0; RP(x, N) { RP(y, M) { if (RD[x][y] != -1 && RD[x][y] <= R && LD[x][y] <= L) { ans++; } } } return ans; }

from http://greedy0110.tistory.com/96 by ccl(A) rewrite - 2021-08-17 02:26:53