반갑습니다!

4485번: 녹색 옷 입은 애가 젤다지? www.acmicpc.net 풀이 경주로 건설 문제와 거의 유사한 문제이다. BFS 알고리즘을 통해서 해결했다. 주의해야할 것은 같은 지점에 위치할 때의 루피의 값이 이전 방향에 따라서 달라질 수 있다는 것이다. BFS외에 다익스트라 알고리즘을 통해서도 해결할 수 있다. 코드 C++ #include #include #include #include #define MAX 987654321 using namespace std; struct Link { int x, y, dir; }; int map[125][125]; int chk[125][125][4]; const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 }; void i..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 일반적인 BFS 알고리즘을 사용해서 목적지까지 가는 경우를 구할 수 있다. 하지만 이 문제에서는 목적지까지 사용되는 최소 금액을 구해야 한다. 문제를 읽어보면 직선 도로 하나 만들 때는 100원, 코너를 하나 만들 때는 500원이 든다. 이 말은 (x, y) 좌표가 있다고 생각했을 때, (x, y)에 도달하기 전 블록에서의 방향과 (x, y)에서 다음 지점으로 나아갈 방향이 같은지 다른지가 금액을 결정한다는 말이다. 그리고 그 말은 한 지금 (x, y)까지 도달하는데 필요한 금액이 (x, y) 지점에 도..

2665번: 미로만들기 www.acmicpc.net 풀이 BFS문제이다. 이동하면서 방의 색을 바꾼다는 점에서 일반적인 문제들과는 차이가 있다 . 일반적인 BFS 문제에서 방문 여부를 확인하던 방식으로 해서는 해결되지 않는다. 검은방을 최소로 바꾸고 끝방으로 가야 하므로 기존에 방문했던 방에 더 적은 수의 검은방을 바꾼 상태로 재 방문할 수 있기 때문이다. 따라서 방문 여부를 체크하는 방식을 수정해야한다. visited[y][x]를 x, y까지 이동하면서 바꾼 검은 방의 수로 정의하여 해결하였다. 그리고 문제에서 방의 정보에 대한 입력값이 띄어쓰기가 되어있지 않으므로 cin이 아닌 scanf("%1d", &map[i][j])를 사용해서 1자리씩 입력받았다. 코드 #include #include #incl..

1194번: 달이 차오른다, 가자. www.acmicpc.net 풀이 이 문제에서는 열쇠를 보유하고 있는 상태를 표시하는 것이 관건인 문제이다. 열쇠 보유 상태를 표현하기 쉽게 하기 위해서 비트 마스킹을 사용했다. a 열쇠를 집은 경우 000001 으로 표기한다. b 열쇠를 집은 경우 000010 으로 표기한다. c 열쇠를 집은 경우 000100 으로 표기한다. d 열쇠를 집은 경우 001000 으로 표기한다. e 열쇠를 집은 경우 010000 으로 표기한다. f 열쇠를 집은 경우 100000 으로 표기한다. 비트 마스킹을 사용하면 여러개의 키를 가지고 있는 경우도 쉽게 표현할 수 있다. 그리고 열쇠를 가지고 있는 경우에 따라서 갈 수 있는 경로가 달라지기 때문에 중복 체크하는 배열을 3차원으로 구성해서..

14502번: 연구소 www.acmicpc.net 풀이 DFS와 BFS를 활용해서 해결하였다. 백트래킹으로 모든 경우의 벽을 세워보고, 벽을 3개 세웠을 경우에 BFS를 통해 빈 칸의 최대 넓이를 구하면 된다. 코드 #include #include #include #include using namespace std; int n, m, blank, ans; int map[8][8]; vector virus; vector blanks; const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 }; int bfs(int count) { bool visited[8][8] = { false, }; queue q; // 큐에 바이러스를 모두 넣는다 for (auto v : ..