18428 감시 피하기
📌문제 링크
https://www.acmicpc.net/problem/18428
💡 문제 풀이
벽을 세 개 세우고 검사한다는 거 보고 14502 연구소 문제랑 비슷하게 풀면 되겠다고 생각했다!
근데 연구소 문제는 바이러스를 퍼뜨리는 과정에서 bfs/dfs를 사용했는데, 여기서는 행과 열의 값만 비교하면 돼서 bfs/dfs를 따로 사용하진 안않았다. (왜 카테고리 분류가 그래프 탐색인거지..?)
연구소 문제와 똑같이 벽을 3개 세우는 함수를 만들어서 풀었는데, 벽을 세우는 모든 경우의 수가 생기지 않는지 자꾸 모든 예시에서 "NO"를 출력했다......
전엔 잘 됐는데 왜,,,
그래서 책 풀이를 참고해 조합을 사용해서 풀었다!
📋코드
# 18428 감시 피하기
import sys
import copy
from itertools import combinations
n = int(input())
arr = [] # 복도의 정보
teacher = [] # 선생님 위치
space = []
for i in range(n):
tmp = list(sys.stdin.readline().split())
arr.append(tmp)
for j in range(n):
if tmp[j] == "T":
teacher.append([i, j])
if tmp[j] == "X":
space.append([i, j])
# 특정 방향으로 감시 진행
# 학생을 발견할 경우 True 리턴, 발견하지 않을 경우 False 리턴
def watch(x, y, direction):
# 왼쪽 방향 감시
if direction == 0:
while y >= 0:
if arr[x][y] == "S":
return True
if arr[x][y] == "O":
return False
y -= 1
# 오른쪽 방향 감시
if direction == 1:
while y < n:
if arr[x][y] == "S":
return True
if arr[x][y] == "O":
return False
y += 1
# 위쪽 방향 감시
if direction == 2:
while x >= 0:
if arr[x][y] == "S":
return True
if arr[x][y] == "O":
return False
x -= 1
# 아래쪽 방향 감시
if direction == 3:
while x < n:
if arr[x][y] == "S":
return True
if arr[x][y] == "O":
return False
x += 1
return False
# 장애물 설치 후 선생님이 학생을 발견할 수 있는지 검사
def process():
for x, y in teacher:
for d in range(4):
if watch(x, y, d):
return True
return False
# 빈 공간의 모든 조합에 대해
for data in combinations(space, 3):
# 장애물 설치하기
for x, y in data:
arr[x][y] = "O"
# 학생을 발견할 수 있는지 검사
if not process():
print("YES")
exit()
# 장애물 다시 없애기
for x, y in data:
arr[x][y] = "X"
print("NO")
16234 인구 이동
📌문제 링크
https://www.acmicpc.net/problem/16234
💡 문제 풀이
처음 문제 읽고 든 생각 : 개복잡하네....
그니까 인접한 나라의 인구 수가 L명 이상, R명 이하라면 국경을 열고
그렇게 연합된 나라끼리는 국민 수를 평균내서 똑같이 나눠가져야 한다는 말이다
연합끼리 국민 수 평균내서 나눠갖고, 그 뒤에 또 인접한 나라끼리 인구 수 L명이상 R명이하 차이인 나라 있으면 또 인구이동 하고... 이렇게 해서 걸리는 시간이 며칠인지를 구해야 한다
나는 dfs로 구현했다
📋코드
# 16234 인구 이동
import sys
from collections import deque
n, l, r = map(int, sys.stdin.readline().split())
a = []
union = []
# 상하좌우 이동
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
for i in range(n):
a.append(list(map(int, sys.stdin.readline().split())))
def dfs(x, y, u, visited):
stack = deque([[x, y]])
visited[x][y] = True
# dfs
while stack:
x, y = stack.pop()
# 상하좌우 이동
for _ in range(4):
nextY = y + dy[_]
nextX = x + dx[_]
# 인덱스가 배열 범위 내인지, 방문하지 않은 국가인지 검사
if 0 <= nextY < n and 0 <= nextX < n and not visited[nextX][nextY]:
# 인구 수 차이가 l이상 r이하일 때
if l <= abs(a[x][y] - a[nextX][nextY]) <= r:
# 연합에 추가
union[u].append((nextX, nextY))
visited[nextX][nextY] = True
stack.append([nextX, nextY])
# 연합 안의 국가 간 인구 이동
def move_people(u):
sum = 0
num = len(u)
for x, y in u:
sum += a[x][y]
for x, y in u:
a[x][y] = sum // num
# 인구 이동에 걸리는 날짜
result = 0
while True:
union = [] # 연합 국가 인덱스를 저장할 배열
uni = 0 # 연합의 개수 index
visited = [[False for _ in range(n)] for _ in range(n)]
# 방문하지 않은 국가일 때 dfs 진행
for i in range(n):
for j in range(n):
if not visited[i][j]:
# 기본적으로 연합에 국가 하나씩은 들어있게 설정
union.append([(i, j)])
dfs(i, j, uni, visited)
uni += 1
# 연합인 국가끼리 인구 이동 수행
for u in union:
# 연합 안에 있는 국가가 1개일 때는 인구이동 하지 않음
if len(u) > 1:
move_people(u)
# 연합의 개수가 n*n개일 때
# 즉, 모든 국가에서 연합이 이루어지지 않았을 때 break
if len(union) >= n*n:
break
else:
result += 1
print(result)
python3로는 시간초과 떴고 pypy3로 통과했다
60058 괄호 변환
📌문제 링크
https://programmers.co.kr/learn/courses/30/lessons/60058
💡 문제 풀이
📋코드
# 60058 괄호 변환
from collections import deque
# u와 v 나누기
def divide(p):
left = 0
right = 0
for i in range(len(p)):
if p[i] == "(":
left += 1
if p[i] == ")":
right += 1
if left == right:
u = p[:i + 1]
v = p[i + 1 :]
return u, v
# 올바른 괄호 문자열인지 확인
def check_right_string(u):
stack = deque()
# 스택으로 괄호 짝이 맞는지 검사했다
for i in range(len(u)):
stack.append(u[i])
if len(stack) >= 2:
if stack[-1] == ")" and stack[-2] == "(":
stack.pop()
stack.pop()
if len(stack) > 0:
return False
else:
return True
# u의 괄호 방향 바꿔주는 함수
def reverse(u):
for i in range(len(u)):
if u[i] == "(":
u[i] = ")"
else:
u[i] = "("
return u
def solution(p):
answer=""
if len(p) == 0:
return ""
u, v = divide(p)
if check_right_string(u):
answer += u
v = solution(v)
return u+v
else:
tmp = "(" + solution(v) + ")"
print("u :", u)
u = reverse(list(u[1:-1])) # 에러 났던 부분
return tmp+"".join(u)
return answer
print(solution("()))((()"))
예제 1이랑 2는 결과 잘 나오는데 예제 3에서 자꾸 에러뜸...
나중에 수정하겠습니다
스터디에서 다른 사람들 코드를 보니 문자열은 변형이 안 돼서 틀리는거였다고 한다..
u = reverse(u[1:-1])를
u = reverse(list(u[1:-1])로 바꿔주니 성공 ㅎㅎ
60063 블록 이동하기
📌문제 링크
https://programmers.co.kr/learn/courses/30/lessons/60063
💡 문제 풀이
bfs로 로봇을 이동시키며 풀면 되겠다고 생각했다
로봇이 [2,1] 크기 모양이라 조금 까다로웠다....
큐에 [(로봇의 왼쪽 좌표), (로봇의 오른쪽 좌표), 여기까지 오는데 걸린 시간] 순서로 push하고 로봇을 움직일 때 마다 벽이 있는지, 움직일 수 있는지 검사하는 방식을 생각했다
풀다 말아서..... (벌금을 내지 않겠다는 마지막 발악)
이것도 나중에 수정하겠습니다ㅠ
📋코드
# 60063 블록 이동하기
from collections import deque
# 상하좌우 이동
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
# 로봇이 가로로 있을 때 90도 회전
# 시계방향 아래로 회전, 반시계방향 아래로 회전 순서
hdx = [1, 1]
hdy = [-1, 1]
# 로봇이 세로로 있을 때 90도 회전
# 시계방향 아래로 회전, 반시계방향 아래로 회전 순서
vdx = [1, 1]
vdy = [1, -1]
def solution(board):
n = len(board)
queue = deque([[(0,0), (0,1), 0]]) # 왼쪽 좌표, 오른쪽 좌표, 걸린 시간
while queue:
left, right, t = queue.popleft()
if left == (n-1, n-1) or right == (n-1, n-1):
return t
# 상하좌우 이동
for _ in range(4):
L_nextX, L_nextY = left[0] + dx[_], left[1] + dy[_]
R_nextX, R_nextY = right[0] + dx[_], right[1] + dy[_]
# 인덱스가 배열 범위 내인지 검사
if 0 <= L_nextX < n and 0 <= L_nextY < n:
if 0 <= R_nextX < n and 0 <= R_nextY < n:
# 이동한 칸에 벽이 없는지 검사
if board[L_nextX][L_nextY] == 0 and board[R_nextX][R_nextY] == 0:
queue.append([(L_nextX, L_nextY), (R_nextX, R_nextY), t+1])
# 90도 회전
if left[0] == right[0] : # 로봇이 가로로 있을 때
for i in range(2):
return answer
board = [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]
print(solution(board))