거울 mirror 문제풀이
1번 풀이방법
import copy
tmp = ""
tmpSplit = []
mirrorList = [] # 거울위치 x,y,dir(/,\)
wareHause = () # 헛간 위치
jhonPoint = (0, 0) #존의 위치
#tmp = input()
#tmpSplit = tmp.split(' ')
#wareHause = (int(tmpSplit[1]), int(tmpSplit[2]))
#for i in range(int(tmpSplit[0])):
# tmp = input()
# tmpSplit = tmp.split(' ')
# mirrorList.append([int(tmpSplit[0]), int(tmpSplit[1]), tmpSplit[2]])
wareHause = (6,2)
mirrorList.append([3, 0, '/'])
mirrorList.append([0, 2, '/'])
mirrorList.append([1, 2, '/'])
mirrorList.append([3, 2, '\\'])
mirrorList.append([1, 3, '\\'])
mirrorList.append([wareHause[0], wareHause[1], "W"]) # 창고를 마지막에 넣어 찾는데 도움을 준다
# 입력값을 모두 입력 받았으니 0,0에서부터 오른쪽을 바라본다
# 순서는 입력받은 mirror를 하나씩 바꾸어보면서 진행한다
# 바꾸지 않아도 되는 경우를 위해 기본 mirror 리스트로 한 번 돌린다
def FindWareHouse(intChangeMirror):
"방향을 바꾸고 싶은 미러의 인덱스를 넣는다"
mirror = copy.deepcopy(mirrorList)
if(intChangeMirror != -1) :
mirror[intChangeMirror][2] = "\\" if mirror[intChangeMirror][2] == "/" else "/" # 해당 번째의 미러 방향 변경
position = [jhonPoint[0], jhonPoint[1]]
return GoWareHouse(position, 4, mirror)
def GoWareHouse(position, direction, changedMirrorList):
"현재 위치와 진행 방향, 거울을 넣는다.(direction up(1), down(2), left(3), right(4))"
if direction == 1: #y-up
for y in range(position[1] + 1, 201):
position[1] = y
for m in changedMirrorList:
if position[0] == m[0] and position[1] == m[1]:
if m[2] == "/":
return GoWareHouse([position[0], y], 4, changedMirrorList)
elif m[2] == "\\" :
return GoWareHouse([position[0], y], 3, changedMirrorList)
else :
return True #헛간
return False
if direction == 2: #y-down
for y in range(position[1] - 1, -1, -1):
position[1] = y
for m in changedMirrorList:
if position[0] == m[0] and position[1] == m[1]:
if m[2] == "/":
return GoWareHouse([position[0], y], 3, changedMirrorList)
elif m[2] == "\\" :
return GoWareHouse([position[0], y], 4, changedMirrorList)
else :
return True #헛간
return False
if direction == 3: #x-down
for x in range(position[0] - 1, -1, -1):
position[0] = x
for m in changedMirrorList:
if position[0] == m[0] and position[1] == m[1]:
if m[2] == "/":
return GoWareHouse([x, position[1]], 2, changedMirrorList)
elif m[2] == "\\" :
return GoWareHouse([x, position[1]], 1, changedMirrorList)
else :
return True #헛간
return False
if direction == 4: #x-up
for x in range(position[0] + 1, 201):
position[0] = x
for m in changedMirrorList:
if position[0] == m[0] and position[1] == m[1]:
if m[2] == "/":
return GoWareHouse([x, position[1]], 1, changedMirrorList)
elif m[2] == "\\" :
return GoWareHouse([x, position[1]], 2, changedMirrorList)
else :
return True #헛간
return False
status = False
status = FindWareHouse(-1)
if status : print("0")
else :
for m in range(len(mirrorList) - 1):
status = FindWareHouse(m)
if status : print(m + 1); break
if status == False:
print("-1")
2번 풀이방법
#-*- coding: utf-8 -*-
from collections import namedtuple
Pos = namedtuple('Pos', ['x', 'y'])
Mirror = namedtuple('Mirror', ['x', 'y', 'type'])
Node = namedtuple('Node', ['x', 'y', 'dir'])
dirmap = {'u' : ('r', 'l'), 'd' : ('l', 'r'), 'r' : ('u', 'd'), 'l' : ('d', 'u'), }
def solve(mlist):
if next(Node(0, 0, 'u'), mlist[:]):
return 0
if next(Node(0, 0, 'r'), mlist[:]):
return 0
for mir in mlist[:-1]:
idx = mlist.index(mir)
nlist = mlist[:]
nm = Mirror(nlist[idx].x, nlist[idx].y, '\\' if nlist[idx].type == '/' else '/')
del nlist[idx]
nlist.insert(idx, nm)
if next(Node(0, 0, 'u'), nlist):
return idx + 1
if next(Node(0, 0, 'r'), nlist):
return idx + 1
return -1
def next(node, mlist):
comparemap = {'u' : lambda mir : node.x == mir.x and node.y < mir.y,
'd' : lambda mir : node.x == mir.x and node.y > mir.y,
'r' : lambda mir : node.x < mir.x and node.y == mir.y,
'l' : lambda mir : node.x > mir.x and node.y == mir.y}
if node.dir == 'u' or node.dir == 'd':
slist = sorted(mlist, key=lambda mir : mir.x, reverse = (True if node.dir == 'd' else False))
else: # node.dir == 'r' or node.dir == 'l'
slist = sorted(mlist, key=lambda mir : mir.y, reverse = (True if node.dir == 'l' else False))
findlist = filter(comparemap[node.dir], slist)
if not findlist: # 패스를 찾을 수 없는 경우
return False
mir = findlist[0]
if mir.type == '-': # barn을 찾은 경우
return True
mlist.remove(mir)
dir = dirmap[node.dir][0 if mir.type == '/' else 1]
return next(Node(mir.x, mir.y, dir), mlist)
def main():
def posparse(line):
x, y = line.split(',')
return Pos(int(x), int(y))
def mirrorparse(line):
x, y, t = line.split(',')
return Mirror(int(x), int(y), t)
barn = posparse(raw_input("Barn (x, y) : "))
cnt = int(raw_input("Count (n) : "))
mlist = []
for i in range(cnt):
mlist.append(mirrorparse(raw_input("Mirror (x, y, type) : ")))
mlist.append(Mirror(barn.x, barn.y, '-'))
result = solve(mlist)
print(result)
def test():
barn = Pos(8, 11)
mlist = [Mirror(0, 3, '/'), Mirror(5, 3, '\\'), Mirror(5, 9, '/'), Mirror(8, 9, '/')]
mlist.append(Mirror(barn.x, barn.y, '-'))
result = solve(mlist)
print(result)
if __name__ == '__main__':
# main()
test()