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 |
Tags
- Nonhomogeneous ODEs
- vocabulary
- 맛집
- 미방
- Ode
- Homogeneous ODEs
- 미분방정식
- English
- 문제풀이
- ODEs
- 영어회화
- 공수1
- Python
- kreyszig
- 공수 문제풀이
- Problem set 2.7
- Advanced Engineering Mathematics
- 대학
- 공학수학
- homogeneous
- 비제차 상미분 방정식
- Conversation
- 공업수학
- Problem Set 1.4
- 삼성SW역량테스트
- 백준
- Problem set 1.5
- 공수
- SW역량테스트
- 코딩테스트
Archives
- Today
- Total
한걸음
백준 1986 : 체스 본문
반응형
https://www.acmicpc.net/problem/1986
1986번: 체스
첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1 ≤ n, m ≤ 1000) 그리고 둘째 줄에는 Queen의 개수와 그 개수만큼의 Queen의 위치가 입력된다. 그리고 마찬가지로 셋째 줄에는 Knight의 개수와 위치,
www.acmicpc.net
https://github.com/HPYoo/swcodingtest/commit/c4b53372868bc132acecf7b0aa1287a7e89d0138
sw coding 1986 update(Baekjoon) · HPYoo/swcodingtest@c4b5337
Showing 1 changed file with 74 additions and 0 deletions.
github.com
1. 퀸의 이동경로를 조심하자!
아무생각 없이 BFS 로 짰다가 퀸끼리 경로가 겹쳐서 더 이상 진행을 안하고 빈곳으로 처리되는 것을 뒤늦게 알았다.
덕분에 한참 헤맸다. 아래와 같은 경우를 보면,
각 퀸이 진행하다가 경로가 겹치는 경우에는 통과할 수 있어야 한다. 물론 나이트의 이동경로와도 겹칠때 퀸은 그 넘어서까지 진로 결정이 가능하다. 그래서 퀸의 경우 다음 칸의 정보가 0이거나 1일 때를 나누어서 진행시켰다. 이점을 제외하면 전형적인 BFS 문제이다.
if board[nx][ny] == 0 and not visited[nx][ny]:
board[nx][ny] = 1
k += 1
check = True
elif board[nx][ny] == 1 :
k += 1
check = True
2. 전체코드
메모리 : 130860 KB, 시간 : 184 ms, 풀이시간 : 60 min
n, m = map(int, input().split())
queen = list(map(int, input().split())) # 2
knight = list(map(int, input().split())) # 3
pawn = list(map(int, input().split())) # 4
board = [[0 for _ in range(m)] for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]
# 상, 상우, 우, 우하, 하, 하좌, 좌, 좌상
# 0, 1, 2, 3, 4, 5, 6, 7
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
q_path = [[0, 2, 4, 6], [1, 3, 5, 7]]
# [상, 상우], [우, 상우], [우, 우하], [하, 우하], [하, 하좌], [좌, 하좌], [좌, 좌상], [상, 좌상]
k_path = [[0, 1], [2, 1], [2, 3], [4, 3], [4, 5], [6, 5], [6, 7], [0, 7]]
def bfs():
# Setting
q = []
if queen[0] != 0 :
for i in range(1, len(queen) - 1, 2):
x, y = queen[i] -1, queen[i + 1] -1
q.append([x, y, 2])
board[x][y] = 2
visited[x][y] = True
if knight[0] != 0 :
for i in range(1, len(knight) - 1, 2):
x, y = knight[i] - 1, knight[i + 1] - 1
q.append([x, y, 3])
board[x][y] = 3
visited[x][y] = True
if pawn[0] != 0 :
for i in range(1, len(pawn) - 1, 2) :
x, y = pawn[i] - 1, pawn[i + 1] - 1
board[x][y] = 4
visited[x][y] = True
while q :
x, y, piece = q[0]
del q[0]
if piece == 2 :
for i in q_path :
for d in i :
k = 1
check = True
while True :
nx = x + k * dx[d]
ny = y + k * dy[d]
if 0 <= nx < n and 0 <= ny < m :
if board[nx][ny] == 0 and not visited[nx][ny]:
board[nx][ny] = 1
k += 1
check = True
elif board[nx][ny] == 1 :
k += 1
check = True
else :
check = False
else : check = False
if not check : break
if piece == 3 :
for i in k_path :
nx = x + dx[i[0]] + dx[i[1]]
ny = y + dy[i[0]] + dy[i[1]]
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] :
if board[nx][ny] == 0 :
visited[nx][ny] = True
board[nx][ny] = 1
result = 0
for i in range(n):
result += board[i].count(0)
return result
print(bfs())
반응형
'Coding Test' 카테고리의 다른 글
백준 1941 : 소문난 칠공주(Python) (2) | 2023.12.11 |
---|---|
백준 2210 : 숫자판 점프 (1) | 2023.12.06 |
백준 7562 : 나이트의 이동 (1) | 2023.12.04 |
백준 2234 : 성곽 (3) | 2023.11.29 |
백준 2468 : 안전영역 (2) | 2023.11.25 |