[Programmers] 방의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/49190

프로그래머스

 

1. Python

def solution(arrows):
    ret = 0
    dy = [-1, -1, 0, 1, 1, 1, 0, -1]
    dx = [0, 1, 1, 1, 0, -1, -1, -1]
    y, x = 0, 0
    nodes = set()
    nodes.add((0, 0))
    edges = set()
    for arrow in arrows:
        for _ in range(2):
            ny, nx = y + dy[arrow], x + dx[arrow]
            if (ny, nx) in nodes and (y, x, ny, nx) not in edges:
                edges.add((y, x, ny, nx))
                edges.add((ny, nx, y, x))
                ret += 1
                y, x = ny, nx
            else:
                nodes.add((ny, nx))
                edges.add((y, x, ny, nx))
                edges.add((ny, nx, y, x))
                y, x = ny, nx
    return ret

 

2. C++

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(vector<int> arrows) {
    int ret = 0;
	int dy[8] {-1, -1, 0, 1, 1, 1, 0, -1};
	int dx[8] {0, 1, 1, 1, 0, -1, -1, -1};
	int y = 0, x = 0;
	set<vector<int>> nodes;
	set<vector<int>> edges;
	nodes.insert({0, 0});
	for (int d : arrows) {
		for (int i=0; i<2; i++) {
			int ny = y + dy[d], nx = x + dx[d];
			if (nodes.find({ny, nx}) != nodes.end() and edges.find({y, x, ny, nx}) == edges.end()) {
				edges.insert({y, x, ny, nx});
				edges.insert({ny, nx, y, x});
				ret++;
				y = ny;
				x = nx;
			} else {
				nodes.insert({ny, nx});
				edges.insert({y, x, ny, nx});
				edges.insert({ny, nx, y, x});
				y = ny;
				x = nx;
			}
		}
	}
    return ret;
}