BOJ 백준 파이썬 4179 불!
역시 다국어가 적혀있는 문제는 전형적인 풀이법보다는
참신한 느낌이 강하다.
물론 웬만한 골드 문제는 전형적인 풀이법(개념) + ALPHA가 필요한 것 같다.
이 ALPHA 때문에 긴장해야하고 집중해야한다.
이 문제 역시도 ALPHA가 있는 문제였다.
지훈이와 불은 동 시간대에 같이 움직인다.
그러니 불 먼저 움직여야한다. 왜냐면 지훈이 먼저 이동 시키면
지훈이가 이동하고 지훈이가 이동한 곳에 불이 퍼지면 처치곤란이기 때문이다.
그래서 불 먼저 이동시키고 지훈이는 불이 퍼지지 않은 곳으로 이동시킨다.
그래서 시작할때 불 먼저 찾아서 큐에 집어넣고 그 다음에 지훈이 찾아서 큐에 집어 넣은 상태로 시작한다.
ex)불(0초)->지훈(0초)->불(1초)->불(1초)->지훈(1초)->불(2초)->불(2초)
나는 코드 설계를
1)불인 경우
#가 아니면 불을 퍼트림
2)지훈인 경우
.이면 이동 가능
으로 했는데
큐에 (불,x좌표,y좌표) 또는 (지훈,x좌표,y좌표) 식으로
불이면 불을 퍼트리고 지훈이면 지훈이를 이동시키는 식으로 설계했다.
그리고 지훈이면 dist배열을 이용해 값을 추가시켰고
마지막에 0행,n-1행,0열,n-1열 중 -1이 아니면서 가장 작은 값에 +1 한 값을 출력시켜줬다.
이번 문제는 한 번만에 성공했는데 지훈이 대신 불 먼저 이동시키고
큐에 좌표 말고도 불 또는 지훈이를 구별할 수 있는 인자를 집어 넣었다는 점이
ALPHA적인 면이 있어서 시험장에서도 같은 문제가 나오면 쉽게 발상할 수 있을까 생각이 들었다.
더 연습해서 숙련도를 올리는 것이 살 길이다.
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
import sys
from collections import deque
from itertools import combinations
from typing import List, Literal
if __name__=='__main__':
#sys.stdin=open("input2.txt", "rt")
r,c=map(int,input().split()) ##r=행 c=열
board=[list(map(str,input())) for _ in range(r)]
q=deque()
dist=[[-1]*c for _ in range(r)]
## 불 찾기
for i in range(r):
for j in range(c):
if board[i][j]=='F':
q.append(('FIRE',i,j))
#dist[i][j]=0
##지훈이 찾기
for i in range(r):
for j in range(c):
if board[i][j]=='J':
q.append(('JIHUN',i,j))
dist[i][j]=0
dx=[0,0,-1,1]
dy=[1,-1,0,0]
while q:
z,x,y=q.popleft()
#for i in range(r):
# for j in range(c):
# print('%-3s'%board[i][j],end=' ')
# print()
#print()
for k in range(4):
nx=x+dx[k]
ny=y+dy[k]
if 0<=nx<r and 0<=ny<c:
if z=='FIRE': ##불인 경우
if board[nx][ny]=='.' or board[nx][ny]=='J': ##불을 퍼트릴 수 있는 경우
board[nx][ny]='F'
q.append(('FIRE',nx,ny))
else: ##지훈인 경우
if board[nx][ny]=='.':
if dist[nx][ny]==-1:
dist[nx][ny]=dist[x][y]+1
q.append(('JIHUN',nx,ny))
#for i in range(r):
# for j in range(c):
# print('%-3d'%dist[i][j],end=' ')
# print()
min_exit=float('inf')
##행은 고정
for j in range(0,c):
if dist[0][j]!=-1:
min_exit=min(min_exit,dist[0][j])
if dist[r-1][j]!=-1:
min_exit=min(min_exit,dist[r-1][j])
##열은 고정
for i in range(0,r):
if dist[i][0]!=-1:
min_exit=min(min_exit,dist[i][0])
if dist[i][c-1]!=-1:
min_exit=min(min_exit,dist[i][c-1])
#print(min_exit)
if min_exit==float('inf'):
print('IMPOSSIBLE')
else:
print(min_exit+1)
|
cs |