18428 감시 피하기
https://www.acmicpc.net/problem/18428
생각
- 장애물을 세운다 (저번 주차의 연구소와 같은 방식으로)
- 선생님의 위치를 찾는다.
- 해당 위치에서 학생이 보이는지 확인한다
3-1. 해당 위치에서 상하좌우를 그래프 끝까지 탐색한다. 다만 탐색하는 도중 장애물을 만나면 그만 둔다!!
코드
import sys
n=int(sys.stdin.readline().rstrip())
graph=[]
for _ in range(n):
graph.append(list(map(str,sys.stdin.readline().split())))
def find(graph):
#선생님 찾기
for i in range(n):
for j in range(n):
if graph[i][j]=='T':
#print(i,j)
result=see(i,j)
if result==False:
return False
return True
def see(x,y):
#장애물 있는 이상 그 앞은 탐색 하지 않게 하는게 중요 포인트
for i in range(1,n):
#상
if x-i>=0:
if graph[x-i][y]=='O': #장애물을 만나면 그뒤로 탐색 중지
break
elif graph[x-i][y]=='S': #학생을 만나면 바로 false 리턴
return False
for i in range(1,n):
#하
if x+i<n:
if graph[x+i][y]=='O': #장애물을 만나면 그뒤로 탐색 중지
break
elif graph[x+i][y]=='S': #학생을 만나면 바로 false 리턴
return False
for i in range(1,n):
#좌
if y-i>=0:
if graph[x][y-i]=='O': #장애물을 만나면 그뒤로 탐색 중지
break
elif graph[x][y-i]=='S': #학생을 만나면 바로 false 리턴
return False
for i in range(1,n):
#우
if y+i<n:
if graph[x][y+i]=='O': #장애물을 만나면 그뒤로 탐색 중지
break
if graph[x][y+i]=='S': #학생을 만나면 바로 false 리턴
return False
return True
def build_wall(wall): #재귀로 벽을 세우는 모든 경우의 수를 탐색한다.
if wall==3:
res=find(graph) #벽이 세개일 때 dfs 실행
if res==True: #단 한번이라도 True가 나온다면 "YES" 출력 후 프로그램 종료
print("YES")
exit()
return
for i in range(n):
for j in range(n):
if graph[i][j]=='X':
graph[i][j]='O'
build_wall(wall+1)
graph[i][j]='X'
build_wall(0)
print("NO")16234 인구 이동
https://www.acmicpc.net/problem/16234
생각
bfs로 풀어보자...
그래프를 탐색하면서 해당 조건 (두 나라의 인구 차이가 L명 이상, R명 이하)을 충족하면 합쳐준다 -> 이거까진 쉽게 구현 가능했는데
어떻게 인구를 합쳐주는가에 대해서 너무.. 버벅여가지고 교재 코드를 참고하였음!
#인구 이동
import sys
from collections import deque
N,L,R=map(int,sys.stdin.readline().split())
graph=[]
for _ in range(N):
graph.append(list(map(int,sys.stdin.readline().split())))
dx=[-1,1,0,0]
dy=[0,0,-1,1]
total_count=0
def bfs(x,y,index):
united=[] #연합의 위치를 담는 리스트
united.append((x,y))
queue=deque() #bfs 위한 큐
queue.append((x,y))
union[x][y]=index #해당 국가가 현재 연합(및 방문)이 됐는지 안 됐는 지 저장
summary=graph[x][y] #현재 연합의 전체 인구수
count=1 #현재 연합의 국가수
while queue:
x, y = queue.popleft()
for i in range(4):
tx=x+dx[i]
ty=y+dy[i]
if tx>=0 and ty>=0 and tx<N and ty<N and union[tx][ty]==-1:
num=abs(graph[tx][ty]-graph[x][y])
if num>=L and num<=R: #L보다 크거나 같고 R보다 작거나 같을 때 queue삽입
queue.append((tx,ty))
union[tx][ty]=index
count+=1
summary+=graph[tx][ty]
united.append((tx,ty))
#print(x,y,united,summary,count)
for i, j in united: #해당 united에 있는 국가들을 인구 이동시켜준다.
graph[i][j]=summary//count
return count
while True:
index = 0 #몇번째 연합인가
union=[[-1]*N for _ in range(N)]
#print(index,"prev union:",union)
for i in range(N):
for j in range(N):
if union[i][j]==-1: #해당 국가가 이미 연합되지 않았을때만 bfs실행
bfs(i,j,index)
index+=1
#print(index,"next union:",union)
if index==N*N: #연합이 N*N개 라는 뜻 -> 다 합쳐져서 더이상 국경이 열릴 수 없음
break
total_count+=1
print(total_count)60058 괄호 변환
https://programmers.co.kr/learn/courses/30/lessons/60058
생각
그냥 해당 알고리즘대로 구현해주면 되는데
왜 dfs/bfs지?? 하는 생각이 제일 먼저 들은듯....
일단 해당 알고리즘대로 구현을 해주었다.
코드
def is_balance(s): #해당 문자열이 올바른 괄호 문자열인지 확인하는 함수
count=0
for ss in s:
if ss=='(':
count+=1
else:
if count==0:
return False
count-=1
return True
def recursion(w): #재귀
r=0 #(
l=0 #)
u=''
v=''
e=''
s=''
length=len(w)
if length==0:
return ''
for i in range(length): #w를 u와 v로 나눠주는 반복문
if w[i]=='(':
r+=1
elif w[i]==')':
l+=1
if r==l:
u=w[:i+1]
v=w[i+1:]
break
if is_balance(u): #문자열 u가 올바른 괄호 문자열이라면
s=recursion(v) #v를 재귀로 다시 돌려준다
return u+s
else: #u가 올바르지 않은 괄호 문자열이라면
u=list(u[1:-1]) #u의 첫, 마지막 문자 제거
for i in range(len(u)): #나머지 괄호 반대로
if u[i]=='(':
u[i]=')'
else:
u[i]='('
e='('+recursion(v)+')'+"".join(u) #빈 문자열에 (+v재귀+)+변환한 u를 합쳐준다
return e
def solution(p):
answer = ''
answer=recursion(p)
return answer아래 부분이 진심 계~~속 오류가나서 ㅠㅠ 개빡춌는데
else: #u가 올바르지 않은 괄호 문자열이라면
u=list(u[1:-1]) #u의 첫, 마지막 문자 제거
for i in range(len(u)): #나머지 괄호 반대로
if u[i]=='(':
u[i]=')'
else:
u[i]='('
e='('+recursion(v)+')'+"".join(u) #빈 문자열에 (+v재귀+)+변환한 u를 합쳐준다
return eu=list(u[1:-1])
이 부분을 계속
u=u[1:-1]
이렇게 하니까 오류가 나는거였다...
도대체 왜지? 하고 확인해보니
문자열을 함수(replace 등등..)를 사용하지 않는이상 바꾸는게 불가능하다는거였음
그래서 list로 1차 변환해서 괄호를 반대로 바꿔준 후 join함수를 이용해 문자열에 다시 붙여줘야 되는 거였다...
60063 블록 이동하기
https://programmers.co.kr/learn/courses/30/lessons/60063
생각
문제는 진짜 간단한 dfs/bfs 문제!
상하좌우 + 회전의 경우로 구조를 나누는 것 까진 쉽게 했다!
상하좌우는 dy dx로 다뤄주면 됐는데
회전이 너무 헷갈려서 (하...................ㄱ-) 한번 직접 그려보고+교재 코드를 참고 했음
코드
from collections import deque
import copy
dx=[0,0,-1,1]
dy=[-1,1,0,0]
#상하좌우회전!!!
def bfs(board):
n=len(board)
queue=deque()
visited=[] #방문여부 저장해주는 리스트
pos={(0,0),(0,1)} #로봇의 위치를 저장
queue.append((0,pos)) #큐에 시간과 시작 위치를 넣어준다
visited.append(pos) #시작 위치를 방문했다고 해준다.
while queue:
time, pos=queue.popleft() #시간, 로봇의 위치{(x,y),(x,y)}
if (n-1,n-1) in pos: #만약 끝지점에 도달했다면
return time #멈추고 time 리턴
pos = list(pos) #pos를 리스트화 시켜준 후 좌표를 추출해준다.
x1, y1, x2, y2 = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
for i in range(4): #상하좌우 먼저 해결
tx1=x1+dx[i]
ty1=y1+dy[i]
tx2=x2+dx[i]
ty2=y2+dy[i]
if 0<=tx1<n and 0<=ty1<n and 0<=tx2<n and 0<=ty2<n and board[tx1][ty1]==0 and board[tx2][ty2]==0 : #그래프 범위를 넘어가지 않게 && 벽이 아닌 곳만
if {(tx1,ty1),(tx2,ty2)} not in visited: #방문하지 않은 곳인 지 확인 후
queue.append((time+1,{(tx1,ty1),(tx2,ty2)}))
visited.append({(tx1,ty1),(tx2,ty2)}) #큐와 방문여부 배열에 해당 위치를 추가해준다.
#여기서부터는 방향 전환
if x1==x2:#가로 상태에서 방향전환
for i in [-1,1]:
if 0<=x1+i<n and 0<=x2+i<n and board[x1+i][y1]==0 and board[x2+i][y2]==0 :
if {(x1,y1),(x1+i,y1)} not in visited:
queue.append((time+1,{(x1,y1),(x1+i,y1)}))
visited.append({(x1,y1),(x1+i,y1)})
if {(x2,y2),(x2+i,y2)} not in visited:
queue.append((time+1,{(x2,y2),(x2+i,y2)}))
visited.append({(x2,y2),(x2+i,y2)})
else:#세로 상태에서 방향 전환
for i in [-1,1]:
if 0<=y1+i<n and 0<=y2+i<n and board[x1][y1+i]==0 and board[x2][y2+i]==0 :
if {(x1,y1),(x1,y1+i)} not in visited:
queue.append((time+1,{(x1,y1),(x1,y1+i)}))
visited.append({(x1,y1),(x1,y1+i)})
if {(x2,y2),(x2,y2+i)} not in visited:
queue.append((time+1,{(x2,y2),(x2,y2+i)}))
visited.append({(x2,y2),(x2,y2+i)})
def solution(board):
answer = 0
return bfs(board)
괴발개발~