Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 시뮬레이션
- 위상정렬
- 그리디
- 수학
- 후니의 쉽게 쓴 시스코 네트워킹
- 플로이드-와샬
- dfs
- Kotlin
- 동적계획법
- 스택
- 에라토스테네스의 체
- 백트래킹
- 투 포인터
- 세그먼트 트리
- 문자열
- 완전탐색
- 구현
- JUnit 5
- BFS
- 알고리즘
- CS
- swea
- mst
- Network
- 유니온 파인드
- 이분탐색
- java
- 백준
- 프로그래머스
- Effective Java
Archives
반갑습니다!
[백준] 18428 감시 피하기 본문
풀이
순열을 구현해서 3개의 장애물을 설치하고 감시를 피할 수 있는지 확인해주면 된다. c++에서는 DFS를 통해 순열을 구현했고, Python3에서는 combinations()
함수를 사용해서 구현했다.
코드
#include <iostream>
#include <vector>
using namespace std;
int n, answer;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
vector<pair<int, int>> cand, teachers;
char board[6][6];
// 감시 피할 수 있는지 체크하는 함수
int check() {
for (pair<int, int> t : teachers) {
for (int i = 0; i < 4; i++) {
int nx = t.first;
int ny = t.second;
while (true) {
nx += dx[i];
ny += dy[i];
if (nx <0 || nx > n - 1 || ny < 0 || ny > n - 1 || board[ny][nx] == 'O') break;
if (board[ny][nx] == 'S') return 0;
}
}
}
return 1;
}
// DFS 사용해서 장애물 설치
void dfs(int idx, int cnt) {
if (cnt == 3) {
answer += check();
return;
}
for (int i = idx + 1; i < cand.size(); i++) {
int x = cand[i].first;
int y = cand[i].second;
board[y][x] = 'O';
dfs(i, cnt + 1);
board[y][x] = 'X';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> board[i][j];
if (board[i][j] == 'X') cand.push_back({ j, i });
else if (board[i][j] == 'T') teachers.push_back({ j, i });
}
dfs(-1, 0);
if (answer == 0) cout << "NO\n";
else cout << "YES\n";
return 0;
}
Python3
import sys
from itertools import combinations
n = int(sys.stdin.readline().rstrip())
board = [] # 복도 저장 리스트
cand = [] # 빈 공간 저장할 리스트
teachers = [] # 선생님들 위치를 저장할 리스트
for i in range(n):
board.append(list(sys.stdin.readline().rstrip().split()))
for j in range(n):
if board[i][j] == 'X':
cand.append((j, i))
elif board[i][j] == 'T':
teachers.append((j, i))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
answer = 0
# 빈 공간 3개를 선택해 장애물을 설치
def set_obstacles():
for obs in combinations(cand, 3):
for x, y in obs:
board[y][x] = 'O'
global answer
answer += check()
if answer > 0: break
for x, y in obs:
board[y][x] = 'X'
# 감시를 피할 수 있는지 체크하는 함수
def check():
for t in teachers:
for i in range(4):
nx = t[0]
ny = t[1]
while True:
nx += dx[i]
ny += dy[i]
if (nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1 or board[ny][nx] == 'O'):
break
if board[ny][nx] == 'S':
return 0
return 1
set_obstacles()
if answer == 0:
print('NO')
else:
print('YES')
'알고리즘 문제 풀이' 카테고리의 다른 글
[프로그래머스] 두 개 뽑아서 더하기 (0) | 2020.09.22 |
---|---|
[프로그래머스] 삼각 달팽이 (0) | 2020.09.22 |
[백준] 1439 뒤집기 (0) | 2020.09.20 |
[백준] 16479 컵라면 측정하기 (0) | 2020.09.18 |
[백준] 2605 줄 세우기 (0) | 2020.09.17 |