[Programmers] 아이템 줍기

https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=cpp

프로그래머스

 

1. Python

def solution(rectangle, characterX, characterY, itemX, itemY):
    board = [[-1] * 102 for _ in range(102)]
    for r in rectangle:
        x1, y1, x2, y2 = map(lambda x: x*2, r)
        for x in range(x1, x2+1):
            for y in range(y1, y2+1):
                if x1 < x < x2 and y1 < y < y2:
                    board[x][y] = 0
                elif board[x][y] == -1:
                    board[x][y] = 1

    characterX *= 2
    characterY *= 2
    itemX *= 2
    itemY *= 2

    dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
    q = deque()
    q.append((0, characterX, characterY))
    visited = set()
    visited.add((characterX, characterY))
    while q:
        t, x, y = q.popleft()
        if x == itemX and y == itemY:
            return t // 2
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if board[nx][ny] == 1 and (nx, ny) not in visited:
                q.append((t+1, nx, ny))
                visited.add((nx, ny))
    return -1

 

2. C++

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    int board[102][102];
	for (int i=0; i<102; i++) {
		for (int j=0; j<102; j++) {
			board[i][j] = -1;
		}
	}
	for (auto r : rectangle) {
		int x1 = r[0] * 2;
		int y1 = r[1] * 2;
		int x2 = r[2] * 2;
		int y2 = r[3] * 2;
		for (int x=x1; x<x2+1; x++) {
			for (int y=y1; y<y2+1; y++) {
				if (x > x1 and x < x2 and y > y1 and y < y2) {
					board[x][y] = 0;
				}
				else if (board[x][y] == -1) {
					 board[x][y] = 1;
				}
			}
		}
	}
	characterX *= 2;
	characterY *= 2;
	itemX *= 2;
	itemY *= 2;
	
	int dy[4] {0, 1, 0, -1};
	int dx[4] {1, 0, -1, 0};
	
	deque<vector<int>> q;
	q.push_back({0, characterX, characterY});
	set<vector<int>> visited;
	visited.insert({characterX, characterY});
	while (not q.empty()) {
		vector<int> tmp = q.front();
		int t = tmp[0];
		int x = tmp[1];
		int y = tmp[2];
		q.pop_front();
		if (x == itemX and y == itemY) {
			return t / 2;
		}
		for (int d=0; d<4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (board[nx][ny] == 1 and visited.find({nx, ny}) == visited.end()) {
				q.push_back({t+1, nx, ny});
				visited.insert({nx, ny});
			}
		}
	}
	return -1;
	
}