문제 링크
알고리즘: BFS, DFS
문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.
각각의 벽에 대해서 다음을 구해보려고 한다.
벽을 부수고 이동할 수 있는 곳으로 변경한다.
그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
풀이
솔루션은 쉽게 생각이 났다. 그런데 하나의 함수에 모든 걸 처리하려다 보니 몇 번 실패를 겪고 일 처리를 나눠서 하니 쉽게 풀렸다.
이 문제를 벽마다 DFS 또는 BFS를 실행하면 백 프로 TLE가 발생한다. 그래서 인접한 0끼리 묶어서 마크하는 DFS를 한번 실행하고, 마크 표시를 다 마친 맵을 이용해서 각각 벽마다 상하좌우 값을 중복 없이 카운트해 주면 TLE 없이 통과할 수 있다.
소스코드 Java
import java.io.*;
import java.util.*;
class Node {
int x,y,z,c;
Node(int x, int y, int z, int c) {
this.x = x;
this.y = y;
this.z = z;
this.c = c;
}
}
class Coordinate {
int x,y;
Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static final int wx[] = {0,0,-1,1};
static final int wy[] = {-1,1,0,0};
static int map[][];
static int w_map[][];
static Coordinate c_map[][];
static boolean visited[][];
static ArrayList<Coordinate> sc_arr = new ArrayList<Coordinate>();
static int N, M;
static String ans;
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
w_map = new int[N][M];
c_map = new Coordinate[N][M];
for(int i=0; i<N; i++) {
String s = br.readLine();
Arrays.fill(w_map[i], -1);
for(int j=0; j<M; j++) {
map[i][j] = s.charAt(j) - '0';
if(map[i][j] == 0) {
w_map[i][j] = 0;
}
}
}
for(int i=0; i<N; i++) {
for( int j=0; j<M; j++) {
if(w_map[i][j] == 0) {
Coordinate c_start = new Coordinate(j,i);
w_DFS(j,i, c_start);
}
}
}
visited = new boolean[N][M];
StringBuilder sb = new StringBuilder();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j] == 1) {
sb.append(find_route(j,i) % 10);
back_visited();
} else {
sb.append(0);
}
}
if(i!=N-1) {
sb.append("\n");
}
}
System.out.println(sb);
}
static int w_DFS(int x, int y, Coordinate cs) {
w_map[y][x] = 1;
c_map[y][x] = cs;
for(int i=0; i<4; i++) {
int nx = x + wx[i];
int ny = y + wy[i];
if((nx>=0 && nx<=M-1) && (ny>=0 && ny<=N-1)) {
if(w_map[ny][nx] == 0) {
w_map[y][x] += w_DFS(nx, ny, cs);
}
}
}
return w_map[y][x];
}
static int find_route(int x, int y) {
for(int i=0; i<4; i++) {
int nx = x + wx[i];
int ny = y + wy[i];
if((nx>=0 && nx<=M-1) && (ny>=0 && ny<=N-1)) {
if(c_map[ny][nx] != null) {
int sx = c_map[ny][nx].x;
int sy = c_map[ny][nx].y;
if(!visited[sy][sx]) {
visited[sy][sx] = true;
sc_arr.add(new Coordinate(sx,sy));
map[y][x] += w_map[sy][sx];
}
}
}
}
return map[y][x];
}
static void back_visited() {
for(int i=0; i<sc_arr.size(); i++) {
visited[sc_arr.get(i).y][sc_arr.get(i).x] = false;
}
sc_arr = new ArrayList<Coordinate>(); //초기화
}
}소스코드 Javascript
const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let [N,M] = inputData[0].trim().split(' ').map(Number);
let map = Array.from(Array(N), () => Array(M));
let w_map = Array.from(Array(N), () => Array(M).fill(-1));
let c_map = Array.from(Array(N), () => Array(M)) //좌표값 저장
for(let i=1; i<inputData.length; i++) {
let input = inputData[i].trim().split('').map(Number);
for(let j=0; j<input.length; j++) {
map[i-1][j] = input[j];
if(input[j] === 0) {
w_map[i-1][j] = 0;
}
}
}
let wx = [0, 0, -1, 1];
let wy = [-1, 1, 0, 0];
for(let i=0; i<w_map.length; i++) {
for(let j=0; j<w_map[i].length; j++) {
if(w_map[i][j] === 0) {
let c_start = {x:j,y:i}; //시작 좌표 값.
w_DFS(j,i,c_start);
}
}
}
let visited = Array.from(Array(N), () => Array(M).fill(false));
let sc_arr = []; //true 해준 visited를 다시 false로
for(let i=0; i<map.length; i++) {
for(let j=0; j<map[i].length; j++) {
if(map[i][j] === 1) {
fill_wall(j,i);
back_visited();
}
}
}
let answel = '';
for(let i=0; i<map.length; i++) {
for(let j=0; j<map[i].length; j++) {
answel += `${map[i][j]}`;
}
answel += '\n';
}
console.log(answel.trim());
function w_DFS(x,y,cs) {
//인접한 0의 경로를 계산하는 DFS
w_map[y][x] = 1;
c_map[y][x] = cs;
for(let i=0; i<4; i++) {
let nx = x + wx[i];
let ny = y + wy[i];
if((nx>=0 && nx<=M-1) && (ny>=0 && ny<=N-1)) {
if(w_map[ny][nx] === 0) {
w_map[y][x] += w_DFS(nx, ny, cs);
}
}
}
return w_map[y][x];
}
function fill_wall(x,y) {
for(let i=0; i<4; i++) {
let nx = x + wx[i];
let ny = y + wy[i];
if((nx>=0 && nx<=M-1) && (ny>=0 && ny<=N-1)) {
if(c_map[ny][nx] !== undefined) {
let sx = c_map[ny][nx].x;
let sy = c_map[ny][nx].y;
if(!visited[sy][sx]) {
visited[sy][sx] = true;
sc_arr.push({x: sx, y: sy});
map[y][x] += w_map[sy][sx];
}
}
}
}
map[y][x] = map[y][x] % 10
}
function back_visited() {
sc_arr.map((ele) => {
visited[ele.y][ele.x] = false;
})
sc_arr = []; //초기화
}
