문제
형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.
이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.
기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1
4 4
----
----
----
----예제 출력 1
4예제 입력 2
6 9
-||--||--
--||--||-
|--||--||
||--||--|
-||--||--
--||--||-예제 출력 2
31예제 입력 3
7 8
--------
|------|
||----||
|||--|||
||----||
|------|
--------예제 출력 3
13예제 입력 4
10 10
||-||-|||-
||--||||||
-|-|||||||
-|-||-||-|
||--|-||||
||||||-||-
|-||||||||
||||||||||
||---|--||
-||-||||||예제 출력 4
41예제 입력 5
6 6
-||--|
||||||
|||-|-
-||||-
||||-|
||-||-예제 출력 5
19문제 해석
# 기훈이 방바닥 나무 판자 필요한 개수
# 나무판자 = 1의 너비/ 양수의 길이
# 기훈이 방 = 직사각형모양 / 벽과 평행한 모양의 정사각형
# -, |로 이루어진 바닥장식 모양
# if -- and 같은행(가로) => 같은 나무 판자
# if || and 같은 열(세로) => 같은 나무 판자어쨋든 나무판자 개수를 구하면 된다
근데 여기서 -- 두개까지 1개의 나무판자
|
|
2개까지 1개의 나무판자로 문제를 해석했는데
입력 출력 값을 확인해보니 그냥 ----- 나 ||||가 세로로 이어져있으면 안끊어진다는 가정하에 1개로 취급한다는걸 예제로 알게되었다.
# 첫째줄 = 세로 N 가로 M(50~이하)
# 둘째줄 = N개의 줄 + M개의 문자(바닥 장식[ - or | ])여기서 풀다보니 bfs가 익숙해서 deque에 넣어서 풀려고 시도했으나,
이문제는 좌표로 이중배열을 만들어서 - 기준 우측, |기준 아래측으로만 이동하면 되는 문제여서 조금은 더 난이도가 쉽지만 기존 풀던 방식을 변형해야만 풀 수 있는 문제였다.
N, M = map(int, input().split())일단 mapping해서 int화 시킨 N,M양의 정수를 받아옴
floor = [input().rstrip() for _ in range(N)]N줄만큼 반복하며 한줄 기준 strip으로 띄워쓰기 기준만큼 넣어주는데,
여기서 처음 rstrip을 사용해봤다
rstrip이란?
<<문자열>>의 오른쪽 끝에 있는 공백 혹은 특정 문자를 제거하는 문자열 메서드
원래 문자열을 수정하지 않고, 수정된 새로운 문자열을 반환합니다
- 공백 제거
- 특정 문자 제거
text = 'hello!!' result = text.rstrip('!') print(result) # 'hello'
- 여러 문자 제거 (ex- '?!')
# 방문 흔적
visited = [[False]*M for _ in range(N)]한번이라도 체크한 곳은 True로 만들기 위한 False 이중 배열
def dfs(x, y):
# 현재 위치를 방문 처리
visited[x][y] = True
# 가로 판자 ('-')일 경우 오른쪽으로 탐색
if floor[x][y] == '-':
while y < M and floor[x][y] == '-':
if not visited[x][y]:
visited[x][y] = True
y += 1
return # 오른쪽 끝에 도달하면 종료
# 세로 판자 ('|')일 경우 아래쪽으로 탐색
elif floor[x][y] == '|':
while x < N and floor[x][y] == '|':
if not visited[x][y]:
visited[x][y] = True
x += 1
return # 아래쪽 끝에 도달하면 종료
# 모든 칸을 탐색
for i in range(N):
for j in range(M):
# 방문하지 않은 판자를 발견하면 DFS 실행
if not visited[i][j]:
dfs(i, j)
count += 1 # 새로운 판자를 발견할 때마다 count 증가
# 결과 출력
print(count)
이 부분이 난 아직 헤깔리고 어려운데,
한 줄 한줄 분석해보겠다.
일단 x,y좌표에 접근하면 무조건 방문했으므로 True로 변환
그리고 해당 위치가 '-'라면,
while문을 통해 y<M까지(0부터 인덱스 시작이므로),
그리고 위치바뀐 floor[x][y]도 '-'일때라면,
근데 if문의 not visited도 while문에 넣어도 되지 않나? 궁금했다
if floor[x][y] == '-':
while y < M and floor[x][y] == '-':
if not visited[x][y]:
visited[x][y] = True
y += 1
return # 오른쪽 끝에 도달하면 종료
이것과
# 가로 판자 ('-')일 경우 오른쪽으로 탐색
if floor[x][y] == '-':
while y < M and floor[x][y] == '-' and not visited[x][y]:
visited[x][y] = True
y += 1
return # 오른쪽 끝에 도달하면 종료무슨 차이가 있는지 상세히 살펴보면,
첫번째 while문은 조건이 참이면 반복문 실행
즉, y<M조건 충족하고?
floor[x][y] == '-'인것도 충족하면
아래 로직을 실행할 수 있음
근데 아래 로직은
아직 방문 안했을때까지 조건을 따져야 visited를 방문처리를 하고 y좌표 값을 더하주는데,
두번째 while문은 y<M조건이고(무조건 충족),
floor[x][y]=='-'이면서 (당장은 현재 위치)
visited가 방문한적이 없어야한다?
근데 이미 def 함수 안에서 True로 만들어놓고 아래 로직을 비교하는 것이기 때문에,
while 조건이 참일 수가 없다..!
그렇기 때문에
if floor[x][y] =='-':
while y<M and floor[x][y] =='-':
if not visited[x][y]
y += 1이 코드가 맞는데 이것조차 오류가 있다.
왜냐면 애초에 첫 visited[x][y]가 true로 시작하기 때문에 첫번째 while문의 if not조건은 성립하지 않는다.
그럼 쓸모 없이 한번 while문이 돌아간 이후 다음 로직부턴 y+1이여서 if not 조건이 참이되어 다음 visited좌표도 True가 되는데,
비효율적인 코드라 생각된다.
수정하면
def dfs(x,y):
visited[x][y] = True
if floor[x][y] == '-':
ny = y
while ny < M and floor[x][ny] == '-'이것조차 새로운 변수 ny를 굳이 만들어줄 필요가 없다고 생각되어서
def dfs(x,y):
visited[x][y] = True
if floor[x][y] == '-':
while y + 1 < M and floor[x][y+1] =='-':
y += 1
visited[x][y] = True
elif floor[x][y] == '|':
while x + 1 < N and floor[x+1][y] == '|':
x += 1
visited[x][y] = True
이렇게 짜니까 정답이 되었다.. 참 사소한거에서 막혀 나는 ㅠ
for i in range(N):
for j in range(M):
if not visited[i][j]:
dfs(i,j)
count += 1
print(count)그 후 4x4 다 돌아가면서 방문 아직 안되있는 처리되어있으면 나무 이어진것까지 1개로 쳐서 문제를 풀 수 있었다...
참... 이번에 그래도 제대로 코드 짜서 많이 이해가 된 것 같다 굿굿!!
최종 코드
N, M = map(int, input().split())
floor = [input().rstrip() for _ in range(N)]
visited = [[False] * M for _ in range(N)]
count = 0
def dfs(x, y):
visited[x][y] = True
if floor[x][y] == '-':
while y + 1 < M and floor[x][y + 1] == '-':
y += 1
visited[x][y] = True
elif floor[x][y] == '|':
while x + 1 < N and floor[x + 1][y] == '|':
x += 1
visited[x][y] = True
for i in range(N):
for j in range(M):
if not visited[i][j]:
dfs(i, j)
count += 1
print(count)
