백준 17267 상남자

 

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

17267번: 상남자

 

visited[x][y] 을 x,y 에 도착했을떄 남은 L+R의 최대값이 정의했다. (배열을 [L][R]까지 모두 사용하면 메모리 초과한다.)

 

합을 사용해도 되는 이유는 L,R은 사실 독립된 관계가 아니라는 점 한점에서 만나기 위해서는 왼쪽으로 가려면 무조건 오른쪽으로도 가야한다.

 

예를들어 L=10 R =10이라고 치자

 

00000X00

00010000

00020000

 

2에서 X로 가기 위한 경로를 L,R 관점에서 생각해보자 

오른쪽 방향으로 갈때는 L1=10, R1=8이 남는다

왼쪽으로 통해서 갈 때는 L2=9 R2=7이 남는다 

 

L1+R1 = 18 

L2+R2 = 16 이므로 L1+R1>L2+R2 => L1>L2 R1 >R2가 모두 성립한다.

 

일반적으로 생각을 하더라도 왼쪽으로 간 점이 시작점 기준으로 오른쪽 에 잇는 줄에서 만나면 적어도 왼쪽으로 간만큼 오른쪽으로 더 가야한다.(벽 때문에 더 가야 할수도 있지만 덜 갈수는 없다)

그러므로 남는 오른쪽횟수가 적을수 밖에 없다.(왼쪽은 당연히 처음에 한번 썼으므로 더 적다.)

 

즉 Lx+Rx >=Ly+Ry 이면 Lx>=Ly && Rx>=Ry이 성립한다.

 또한 L+R이 이미 방문한 점의 visited[x][y] 작다면 L,R 모두 visited[x][y]을 찍은 점보다 작고, 방문할수있는 지점도 적으므로 더이상 BFS로 진행할 필요가 없다.

 

 

package 백준;

import java.util.*;
import java.io.*;

public class 상남자 {
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
	}

	static class Point {
		int x;
		int y;
		int l;
		int r;

		public Point(int x, int y, int l, int r) {
			this.x = x;
			this.y = y;
			this.l = l;
			this.r = r;
		}

	}

	public static void main(String[] args) {
		MyScanner sc = new MyScanner();

		int N = sc.nextInt();
		int M = sc.nextInt();
		int L = sc.nextInt();
		int R = sc.nextInt();
		int map[][] = new int[N][M];
		Point start = new Point(0, 0, L, R);

		for (int i = 0; i < N; i++) {
			String s = sc.next();
			for (int j = 0; j < M; j++) {
				map[i][j] = s.charAt(j) - '0';
				if (map[i][j] == 2) {
					start.x = i;
					start.y = j;
				}
			}
		}

		Queue<Point> q = new LinkedList<Point>();
		q.add(start);

		int visited[][] = new int[N][M]; 
		boolean answer[][] = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited[i][j] = -1;
			}
		}

		visited[start.x][start.y] = L + R;
		answer[start.x][start.y] = true;

		int dx[] = { -1, 1, 0, 0 };
		int dy[] = { 0, 0, -1, 1 };

		while (!q.isEmpty()) { // BFS
			Point p = q.poll();
			for (int i = 0; i < 4; i++) {
				int nx = p.x + dx[i];
				int ny = p.y + dy[i];
				int nl = p.l;
				int nr = p.r;

				if (nx < 0 || ny < 0 || nx >= N || ny >= M)
					continue;
				if (map[nx][ny] != 0)
					continue;
				if (i == 2)
					nl--;
				if (i == 3)
					nr--;
				if (nl < 0 || nr < 0)
					continue;

				if (visited[nx][ny] >= nr + nl) // 기존 방문보다 L+R 이 작으면 기존방문보다 무조건 갈수 있는게 적음
					continue;

				visited[nx][ny] = nl + nr;
                
				q.add(new Point(nx, ny, nl, nr));

			}
		}

		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (visited[i][j]!=-1)
					cnt++;
			}
		}

		System.out.println(cnt);

	}

}