https://www.acmicpc.net/problem/16918
문제 해결 방법
1. 시간이 1초씩 감에 따라서 봄버맨의 행동과 폭탄의 상태가 달라지니 시간을 변수로 둔다.
2. 봄버맨의 움직임 패턴을 분석한다.
종이에 쓰인 까만색깔 숫자는 시간 초를 의미한다.
봄버맨은의 행동 패턴은 1초 단위로 다음과 같이 흐른다.
설치
->유지(현재 놓여진 폭탄에 대해서만 시간초를 매김=시간증가)
->설치와 동시에 현재 놓여진 폭탄도 시간초를매김 == 모든 좌표값을 +1 해준다.
->폭발
위 패턴을 폭탄 패턴이라 하겠다.
그런데 이게 2초 부터는 폭탄이 설치 되어있지 않은 모든 칸에 또 폭탄을 설치하기 때문에, 2초부터 또다른 폭탄 패턴이 진행된다.
따라서 0초부터 N초 까지는 직사각형 격자판에 2개의 폭탄 패턴이 돌고있다고 보면된다.
이 2개의 서로 다른 초에 시작한 폭탄 패턴을 어떻게 패턴화 할까?
종이에 쓰인 폭탄 패턴을 0초, 1초는 제외해두고 2초부터 N초까지 보면,
증가와 설치, 폭발과 유지, 설치와 증가, 유지와 폭발 이 네가지 패턴이 반복됨을 알 수 있다.
(유지와 폭발, 폭발과 유지는 폭발->유지로 친다. 왜냐하면 폭발이 우선순위이기 때문이다. )
이 네가지 패턴이 등장하는 숫자를 따로 모아보면,
n%4 ==3, n%4 ==1, 이외의 경우로 정리할 수 있다.
이렇게 정리된 경우를 잘 고려해 출력까지 잘 해주면 된다.
코드 구현
틀린 코드
더보기
# 크기 RxC 격자
# 폭탄칸 3초 지난후 폭발 => 폭탄 칸 파괴되어 빈칸됨 => 인접한 네 칸도 파괴됨
# 만약 폭탄 폭발시 인접 네칸에 폭탄이 있는 경우, 해당 폭탄은 폭발없이 파괴됨 = 연쇄반응X
# 1. 일부 칸에 폭탄 설치 = 모든 폭탄이 설치된 시간은 같음 0초
# 2. 다음 1초 동안 아무것도 하지 않음
# 3. 다음 1초 동안 폭탄이 설치되지 않은 모든 칸에 폭탄 설치=모든 칸은 폭탄을 가짐 =동시에 설치
# 4. 1초 지난 후, 3초 전에 설치된 폭탄이 모두 폭발
# 5. 3-4 반복
import sys
input= sys.stdin.readline # 뒤에 괄호 붙이지 않도록 조심.
dy=[0, 0, 1, -1]
dx=[1, -1, 0, 0]
r, c, n = map(int, input().split())
bombMap = []
for i in range(r):
tmp = list(input().strip())
bombMap.append(tmp)
print(bombMap)
time = 0
check=0
for i in range(r):
for j in range(c):
if bombMap[i][j] == '.':
bombMap[i][j]=0
else:
bombMap[i][j]=1
print('초기상태')
print('check', check)
print('time: ', time)
for i in range(len(bombMap)):
print('check', bombMap[i])
print()
realzero=1
while 1:
time+=1
check+=1
if check==1:
if realzero==1:
realzero=0
for i in range(r):
for j in range(c):
if bombMap[i][j] > 0:
bombMap[i][j]+=1
elif realzero ==0:
for i in range(r):
for j in range(c):
bombMap[i][j]+=1
else:
if check ==2 :
for i in range(r):
for j in range(c):
bombMap[i][j]+=1
rem = [item[:] for item in bombMap]
if time >=5:
for i in range(r):
for j in range(c):
if rem[i][j]==3:
bombMap[i][j]=0
for k in range(4):
ni = i + dy[k]
nj = j + dx[k]
if 0<=ni<r and 0<=nj<c:
bombMap[ni][nj]=0
elif check ==3:
for i in range(r):
for j in range(c):
if rem[i][j]==3:
bombMap[i][j]=0
for k in range(4):
ni = i + dy[k]
nj = j + dx[k]
if 0<=ni<r and 0<=nj<c:
bombMap[ni][nj]=0
if time >= n:
print('check', check)
print('time: ', time)
for i in range(len(bombMap)):
print('hello', bombMap[i])
print()
for i in range(r):
tmpS=''
for j in range(c):
if bombMap[i][j]>0:
s='O'
tmpS+=s
else:
s='.'
tmpS+=s
print(tmpS)
break
rem = [item[:] for item in bombMap]
print('check', check)
print('time: ', time)
for i in range(len(bombMap)):
print('hello', bombMap[i])
print()
if check ==3:
check=1
정답 코드
# 크기 RxC 격자
# 폭탄칸 3초 지난후 폭발 => 폭탄 칸 파괴되어 빈칸됨 => 인접한 네 칸도 파괴됨
# 만약 폭탄 폭발시 인접 네칸에 폭탄이 있는 경우, 해당 폭탄은 폭발없이 파괴됨 = 연쇄반응X
# 1. 일부 칸에 폭탄 설치 = 모든 폭탄이 설치된 시간은 같음 0초
# 2. 다음 1초 동안 아무것도 하지 않음
# 3. 다음 1초 동안 폭탄이 설치되지 않은 모든 칸에 폭탄 설치=모든 칸은 폭탄을 가짐 =동시에 설치
# 4. 1초 지난 후, 3초 전에 설치된 폭탄이 모두 폭발
# 5. 3-4 반복
import sys
input= sys.stdin.readline # 뒤에 괄호 붙이지 않도록 조심.
dy=[0, 0, 1, -1]
dx=[1, -1, 0, 0]
r, c, n = map(int, input().split())
bombMap = []
for i in range(r):
tmp = list(input().strip())
bombMap.append(tmp)
time = 0
for i in range(r):
for j in range(c):
if bombMap[i][j] == '.':
bombMap[i][j]=0
else:
bombMap[i][j]=1
# 유지 time ==1
time+=1
for i in range(r):
for j in range(c):
if bombMap[i][j] > 0:
bombMap[i][j]+=1
if n==1:
if time == n:
for i in range(r):
tmpS=''
for j in range(c):
if bombMap[i][j]>0:
s='O'
tmpS+=s
else:
s='.'
tmpS+=s
print(tmpS)
else:
while 1:
time+=1
if time % 4==1:
# 유지
for i in range(r):
for j in range(c):
if bombMap[i][j] > 0:
bombMap[i][j]+=1
rem = [item[:] for item in bombMap]
# 폭발
for i in range(r):
for j in range(c):
if rem[i][j]==3:
bombMap[i][j]=0
for k in range(4):
ni = i + dy[k]
nj = j + dx[k]
if 0<=ni<r and 0<=nj<c:
bombMap[ni][nj]=0
elif time % 4 == 3:
# 폭발
rem = [item[:] for item in bombMap]
for i in range(r):
for j in range(c):
if rem[i][j]==3:
bombMap[i][j]=0
for k in range(4):
ni = i + dy[k]
nj = j + dx[k]
if 0<=ni<r and 0<=nj<c:
bombMap[ni][nj]=0
else:
# 설치, 증가
for i in range(r):
for j in range(c):
bombMap[i][j]+=1
if time == n:
for i in range(r):
tmpS=''
for j in range(c):
if bombMap[i][j]>0:
s='O'
tmpS+=s
else:
s='.'
tmpS+=s
print(tmpS)
break
시간/공간 복잡도
시뮬레이션 문제 같아서 아예 시간복잡도 계산을 배제하고 문제를 풀었다.
최적화 및 개선
- 따로 하지않음
어려웠던 점
- 이 문제는 문제를 풀 때 단순하게 생각하면 안된다.
- 시간을 보내는것과 보내는 중일때 할 일을 잘 구분해야한다.
- 처음에 폭탄 패턴이 두개 돌거란 생각을 하지 못했다. 따라서 문제 자체가 이해 안되고, 심지어 문제에 문제가 있는거 아닌가 하는 생각을 했었다. 항상 무조건 진행 과정에 대해서 헷깔리거나 파악이 안될때 종이에 해당 과정을 손으로 쓰면서 따라가보는게 중요한 것 같다.
- 규칙을 찾아야한다. 규칙을 찾는게 제일 중요한 것 같다.
알게된 것
- sys모듈의 sys.stdin.readLine는 코드로 작성할 때 괄호를 붙이면 안된다.
- sys.stdin.readLine을 사용할때, 뒤에 개행문자가 따라붙는다. 따라서 사용시 주의해줘야한다.
개행문자를 제거하는 함수 사용시 참고할 부분이다.
- strip()이랑 rstrip() 무슨차이인가?
- .strip()과 .rstrip()은 모두 문자열의 양 끝에서 공백 문자를 제거하는 메서드이지만, 제거하는 위치가 다름
- .strip(): 문자열의 앞과 뒤 양쪽에 있는 모든 공백 문자를 제거한다.
- .rstrip(): 문자열의 오른쪽(뒤쪽) 끝에 있는 공백 문자만 제거한다.
- .strip()과 .rstrip()은 모두 문자열의 양 끝에서 공백 문자를 제거하는 메서드이지만, 제거하는 위치가 다름
'코딩테스트 > 문제 풀이 - Python' 카테고리의 다른 글
| [백준10799] 쇠막대기 (0) | 2024.08.09 |
|---|---|
| [백준2110] 공유기 설치 (0) | 2024.08.06 |
| [백준20440] 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 (0) | 2024.08.02 |
| [백준18808] 스티커 붙이기 (0) | 2024.08.01 |
| [백준19637] IF문 좀 대신 써줘 (0) | 2024.07.30 |
