17267번 상남자

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

예전에 한참 고민하고, 고민했던 C++로 풀었던 문제이다.

그 당시에는 queue로 풀려고 하였으나, 계속 틀려서 결국 질문을 통하여 해결하였다.

최대한 자유롭게 움직여서 이동할 수 있는 최대 칸 수를 구하는 문제이므로,

최대가 되기 위해서는 상, 하로 우선 먼저 최대한 많이 움직여야 한다.

따라서, deque를 사용하여 상, 하일 때는 rear이 아닌 front쪽에 push를 해주면 된다.

물론 좌, 우일 때는 rear쪽에 push를 해준다.

또한, 내가 못 풀고 있었을 때의 코드에 대한 반례도 올려본다.

아마 deque로 말고, queue로 구현하였다면, 첫 번째 반례에서 20이 뜰 것이다.

2 왼쪽에 있는 0으로 바로 가기 때문에 L이 0이 되버리기 때문이다.

즉, (2, 3)에 있는 0으로 못 간다.(행과 열은 0부터 시작)

https://www.acmicpc.net/board/view/37868

8 5
1 4
00000
01110
02100
10110
10110
10110
10000
11111
21
 
6 6
1 5
110001
120100
001110
011100
011110
000000
21

하여튼 결국 C++로 구현하였지만,

자바(Java)로도 풀고 싶어서 다시 풀어보았다.

 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, m, L, R, sy, sx;
    static int[][] map;
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static boolean[][] visit;
    
    static int bfs()
    {
        Deque<info> dq = new LinkedList<info>();    
        dq.push(new info(sy, sx, L, R)); // 또는 pushFirst(맨 앞 push)
        visit[sy][sx] = true;
        
        while(!dq.isEmpty())
        {
            int dqs = dq.size();
            
            while(dqs > 0)
            {
                int r = dq.peekFirst().y;
                int c = dq.peekFirst().x;
                int Left = dq.peekFirst().Left;
                int Right = dq.peekFirst().Right;
                
                //System.out.println("(" + r + ", " + c + "), L = " + Left + ", R = " + Right);
                
                dq.pop();
                
                for(int i=0; i<4; i++) {            
                    
                    int y = r + dy[i];
                    int x = c + dx[i];
                    
                    if(y < 0 || y >= n || x < 0 || x >= m || map[y][x] == 1 || visit[y][x]) {
                        continue;
                    }
                                        
                    if(i == 1 || i == 3) {
                        // 상, 하
                        visit[y][x] = true;
                        dq.addFirst(new info(y, x, Left, Right));
                    }
                    else if(i == 0) {
                        // 우
                        if(Right >= 1) {
                            visit[y][x] = true;
                            dq.addLast(new info(y, x, Left, Right - 1));
                        }
                    }
                    else if(i == 2) {
                        // 좌
                        if(Left >= 1) {
                            visit[y][x] = true;
                            dq.addLast(new info(y, x, Left - 1, Right));
                        }
                    }
                }
                
                dqs--;
            }
        }
        
        int ret = 0;
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(visit[i][j]) {
                    ++ret;
                }
            }
        }
        
        return ret;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        map = new int[n+1][m+1];
        visit = new boolean[n+1][m+1];
        
        st = new StringTokenizer(br.readLine());
        
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<n; i++) {
            String s = br.readLine();
            for(int j=0; j<s.length(); j++) {
                map[i][j] = s.charAt(j) - '0';
                if(s.charAt(j) == '2') {
                    sy = i;
                    sx = j;
                }
            }
        }
 
        System.out.println(bfs());
    }
}
 
class info {
    int y, x, Left, Right;
    info(int y, int x, int Left, int Right) {
        this.y = y;
        this.x = x;
        this.Left = Left;
        this.Right = Right;
    }
}