[알고리즘][Python] 백준(BOJ) 1652 누울 자리를 찾아라_파이썬

 

1652 누울 자리를 찾아라    https://www.acmicpc.net/problem/1652

1652번: 누울 자리를 찾아라

 

 

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 수학

 

 

 

문제 풀기 전 힌트

▼ 중간에 어정쩡하게 눕는 경우가 없으므로 '.'이 2개 이상 연달아 있다면 그것은 누울 자리 1개로 생각하면 된다.

 

 

 

 

 

 

 

풀이 1

<내용>

• 누울 자리가 2자리 이상 붙어있으면 누울 자리 1개로 한다.
• 방을 row별로 room에 저장을 한다.
• 방을 돌면서 '.'(누울 수 있는 자리)이 2개 이상 붙어있는 곳을 찾는다.
• cnt를 0으로 초기화하고 방을 돌면서 '.'를 발견하면 cnt에 1을 더한다.
• 그리고 'X'(벽)을 만났을 때
  • cnt가 2 이상이면 누울 수 있는 자리가 있는 것으로 1을 더해준다.
  • cnt('.'의 개수)는 0으로 다시 초기화해야 한다.
• 방의 마지막이
  • 'X'면 문제가 생기지 않는다.
  • '.'이고 cnt가 2 이상이면 누울 수 있는 자리에 1을 더해줘야 하는 문제가 있으므로 j == n-1일 때를 따로 조건을 걸어 해결한다.

 

 

<코드>

n = int(input())
room = []
for _ in range(n):
    room.append(list(map(str, input())))
    
res = [0, 0]
for i in range(n):
    cnt_h, cnt_v = 0, 0
    for j in range(n):
        if room[i][j] == '.':
            cnt_h += 1
        elif room[i][j] == 'X':
            if cnt_h >= 2:
                res[0] += 1
            cnt_h = 0
            
        if room[j][i] == '.':
            cnt_v += 1
        elif room[j][i] == 'X':
            if cnt_v >= 2:
                res[1] += 1
            cnt_v = 0
            
            
        if j == n-1:
            if cnt_h >= 2:
                res[0] += 1
            if cnt_v >= 2:
                res[1] += 1
            
print(' '.join(map(str, res)))

 

+) 위의 코드에서 j == n-1일 때를 구분하지 않고 '.'과 'X'에 관한 조건문으로 해결하는 방법 찾아보기

 

 

 

 

 

풀이 2

<내용>

• 위의 코드에서 j == n-1일 때를 따로 조건을 걸지 않기 위해서 방의 가로와 세로의 끝에 'X'를 추가해서 만든다.
• room에 row를 추가할 때 ['X']를 추가하여 마지막에 j == n-1일 때를 확인하지 않아도 '.' 개수를 초기화하고 마지막이 'X'가 아닐 때, '.'가 2개 이상이면 누울 수 있는 자리에 추가하도록 한다.
• row 마지막에 ['X']를 추가하고 나서 ['X'] * (n+1)를 방에 넣어 세로로 확인할 때도 j == n-1일 때를 확인하지 않아도 누울 수 있는 자리를 셀 수 있도록 한다.
• 다른 논리는 위의 내용과 동일하다.

 

• 이때, for문에서 range의 범위를 n+1로 해야 마지막에 직접 추가한 'X'까지 반복을 하므로 빠지는 자리가 없다.

 

 

<코드>

n = int(input())
room = []
for _ in range(n):
    room.append(list(map(str, input())) + ['X'])
room.append(['X' for _ in range(n+1)])
    
res = [0, 0]
for i in range(n+1):
    cnt_h, cnt_v = 0, 0
    for j in range(n+1):
        if room[i][j] == '.':
            cnt_h += 1
        elif room[i][j] == 'X':
            if cnt_h >= 2:
                res[0] += 1
            cnt_h = 0
            
        if room[j][i] == '.':
            cnt_v += 1
        elif room[j][i] == 'X':
            if cnt_v >= 2:
                res[1] += 1
            cnt_v = 0
            
print(' '.join(map(str, res)))